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’.


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:







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