Time Complexity

Notations

Big O-upper bound

Big Ω-lower bound

Knowing the upper and lower bound helps us make choices when deciding which algorithm is better to use

O(1) - Look-up table (on average)

O(log(n)) - finding element on sorted array with binary search

O(n) - Find max element in unsorted array

O(nlogn) - Sorting elements in array with merge sort

O(n²) - Sorting an array with bubble sort

O(2^n) - find all subsets

O(n!) - find all permutation of a given set/string

Examples

   for(int i=1;i<n;i++){
	for(int j=1;j<m;j++){
		sum = sum+1;
	}
}

This is O(nm)