Google

Apr 14, 2014

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


Labels: ,

1 Comments:

Blogger Unknown said...

Best tutorials ever on JAVA

1:31 AM, October 02, 2014  

Post a Comment

Subscribe to Post Comments [Atom]

<< Home