Understanding Big O notations through Java examples

Q. Have you seen job advertisements requiring Java candidates to work in real-time or high volume transaction processing systems?

If you are applying for such jobs, you can be quizzed on Big O notation. Here are some basics to brush up on.

Big-O gives you the upper bound. For example, if you need to search an element in an array and you expect the array to be large, you might just say that you opt for a binary search instead of a sequential scan because the former has O(log n) complexity wheres the latter has O(n) complexity.

Big-O	Description/Example	If n=10, and c=2	If n=20, and c=2
O(1) Constant	Running time is constant. Determining if a String is equal to a given value if(str.equals("java")) { return true; } else { return false; } A Map look up by key -- map.get(key);	1	1
O(log n) Logarithmic	Running time increases logarithmically in proportion to the input size. Finding an item in a sorted array with a binary search For example, search for 2 in a list of numbers 1,2,3,4,5,6,7 Step 1: Sort the data set in ascending order as binary search works on sorted data. Step 2: Get the middle element (e.g. 4) of the data set and compare it against the search item (e.g. 2), and if it is equal return that element Step 3: If search item value is lower, discard the second half of the data set and use the first half (e.g. 1,2,3). If the search item value is higher, then discard the first half and use the second half (e.g. 5,6,7) Step 4: Repeat steps 2 and 3 until the search item is found or the last element is reached and search item is not found. So, it is iteratively reducing the number of elements it process.	log 10 = 1	log 20 = 1.301
O(n)  Linear	Running time increases in direct proportion to the input size Finding an item in an unsorted array or list. for(int i = 0; i < strings.Length; i++) { if(strings[i].equals("java")) { return true; } else { return false; } }	10	20
O(n log n)  Super linear	Running time is midway between a linear algorithm and a polynomial algorithm Collections.sort is an optimized merge sort which actually guarantees O(n log n). A quicksort is generally considered to be faster than a merge sort (i.e. n log n) but isn't stable and doesn't guarantee n log(n) performance. For Merge sort worst case is O(n*log(n)), for Quick sort: O(n^2).	10 log 10 = 10	20 log 20 = 26.02
O(n^c)  Polynomial	Running time grows quickly based on the size of the input. O(n^2) Quadratic -- bubble Sort (worst case or naive implementation) for(int i = 0; i < strings.Length; i++){ for(int j = 0; j < strings.Length; j++) if(i == j) // Don't compare with self { continue; } if(strings[i].equals(strings[j])) { return true; } else { return false; } }	10^2 = 100	20^2 = 400
O(c^n)  Exponential	Running time grows even faster than a polynomial algorithm. Recursive computation of Fibonacci numbers is a good example of O(2^n) algorithm public int fib(int n) { if (n <= 1) return n; else return fib(n - 2) + fib(n - 1); }	2^10 = 1,024	2^20 = 1,048,576
O(n!) Factorial	Running time grows the fastest and becomes quickly unusable for even small values of n. Recursive computation of factorial public void nFactorial(int n) { for(int i=0; i<n; i=n-1) { nfactorial(i); }	10! = 10*9*8*7*6*5*4*3*2*1= 3,628,800	20!= 2432902008176640000