Big O Notation is a means of theoretically measuring the resources needed to perform an algorithm of ‘n’ inputs. Resources can be a variety of measurements, but most often is time, space, or memory. Essentially, Big O Notation is an algorithm’s efficiency as its input approaches infinity. It is not, however, a means of exactly measuring an algorithm given a specific input. The levels of efficiency, from most to least efficient, are:

- O(1) – Constant
- O(log n) – Logarithmic
- O(n) – Linear
- O(n log n) – “n log n”
- O(n ^
^{2}) – Quadratic - O(a ^
^{n})(a > 1) – Exponential

To find the Big O of an algorithm, count the number of touches, simplify the resulting polynomial, and discard any constants. The answer will then be the fastest growing ‘n’.

Examples:

for(int i = 0; i < n; i++) //touches ‘n’ times

{

}

**F(n) = O(1 + n)** //1 is the constant for engaging the for loop, ‘n’ is the number of times the loop is ‘touched’

**F(n) = O(n)** //Drop the constant. The Big O of this loop is n, or linear.

for(int i = 0; i < n; i++)

{

}

for(int i = 0; i < n; i++) //touches ‘n’ times

{

for(int j = 0; j < n; j++) //touches ‘n’ times

{

}

}

**F(n) = O(1 + n + n * n)** //1 is the constant, the first ‘n’ is the solitary loop, nested loops cause ‘n’s to be multiplied together

**F(n) = O(1 + n + n ^ ^{2})** //Simplify

**F(n) = O(n + n ^ ^{2})** //Drop the constant

**F(n) = O(n ^ ^{2})** //The answer is the fastest growing ‘n’. The Big O of this algorithm is n

^{2}, or quadratic.

Helpful Links:

http://www.dreamincode.net/forums/topic/125427-determining-big-o-notation/

http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it

http://www.apcomputerscience.com/apcs/misc/BIG-O.pdf

http://www.cprogramming.com/tutorial/computersciencetheory/algorithmicefficiency3.html

http://en.wikipedia.org/wiki/Big_O_Notation