2 Week Project on Big O Notation

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 n2, 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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s