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

In mathematics, computer science, and related fields, big-O notation (also known asbig Oh notation, big Omicron notation, Landau notation, Bachmann–Landau notation, and asymptotic notation) (along with the closely related big-Omega notation, big-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(N²)

O(N²) 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(N³), O(N⁴) 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(2^N)

O(2^N) denotes an algorithm whose growth will double with each additional element in the input data set. The execution time of an O(2^N) function will quickly become very large.

Comparing the common notation examples:
(Thanks to Algorithms: Big-Oh Notation.)

n	Constant  O(1)	Logarithmic O(log n)	Linear O(n)	Linear Logarithmic O(n log n)	Quadractic O(n2)	Cubic O(n3)
1	1	1	1	1	1	1
2	1	1	2	2	4	8
4	1	2	4	8	16	64
8	1	3	8	24	64	512
16	1	4	16	64	256	4,096
1,024	1	10	1,024	10,240	1,048,576	1,073,741,824
1,048,576	1	20	1,048,576	20,971,520	1012	1016

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