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
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 |
Labels: Coding, Performance
1 Comments:
Best tutorials ever on JAVA
Post a Comment
Subscribe to Post Comments [Atom]
<< Home