Monday, October 27, 2014

A Beginner’s Guide to Big O Notation (Based on existing resources - see the links below for more infomation)

In mathematicscomputer science, and related fields, big-O notation (also known asbig Oh notationbig Omicron notationLandau notationBachmann–Landau notation, and asymptotic notation) (along with the closely related big-Omega notationbig-Theta notation, and little o notation) describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.


http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

O(1)

O(1) describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.
bool IsFirstElementNull(String[] strings)
{
 if(strings[0] == null)
 {
  return true;
 }
 return false;
}

O(N)

O(N) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. The example below also demonstrates how Big O favours the worst-case performance scenario; a matching string could be found during any iteration of the for loop and the function would return early, but Big O notation will always assume the upper limit where the algorithm will perform the maximum number of iterations.
bool ContainsValue(String[] strings, String value)
{
 for(int i = 0; i < strings.Length; i++)
 {
  if(strings[i] == value)
  {
   return true;
  }
 }
 return false;
}

O(N2)

O(N2) represents an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set. Deeper nested iterations will result in O(N3), O(N4) etc.
bool ContainsDuplicates(String[] strings)
{
 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] == strings[j])
   {
    return true;
   }
  }
 }
 return false;
}

O(2N)

O(2N) denotes an algorithm whose growth will double with each additional element in the input data set. The execution time of an O(2N) function will quickly become very large.
Comparing the common notation examples:
(Thanks to Algorithms: Big-Oh Notation.)
nConstant 
O(1)
Logarithmic
O(log n)
Linear
O(n)
Linear Logarithmic
O(n log n)
Quadractic
O(n2)
Cubic
O(n3)
1111111
2112248
412481664
81382464512
161416642564,096
1,0241101,02410,2401,048,5761,073,741,824
1,048,5761201,048,57620,971,52010121016
Reference : http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
http://www.princeton.edu/~achaney/tmve/wiki100k/docs/Big_O_notation.html
http://www.javacodegeeks.com/2011/04/simple-big-o-notation-post.html

..