Java

TOPIC i06 – ALGORITHM COMPLEXITY & THE BIG O NOTATION

 

 

LESSON NOTE

 

 

MEASURING COMPLEXITY

It is important to understand that two students can come up with two different solutions to a programming problem.  While both solutions may work, one may be much more complexe (and less efficient) than the other.

 

This complexity is very important.  It can make the difference between a program taking hours to do a calculation or a program taking just seconds to do the same calculations.

 

Complexity is very important when dealing with programs that deal with large amounts of data (often arrays).

 

SORTING ARRAYS = COMPLEXITY ISSUE

 

Different sorting algorithms have very different complexities which in turn lead to very different computational time.  We will see this in the work section.

 

MEASURING COMPLEXITY

 

One simple way to measure complexity would be to count the number of statements in a snippet of code.

 

So a piece of code with 10 statements should be less complex than a piece of code with 25 statements.

 

Of course, this does require that we make a major assumption that each statement is about equivalent to any other statements.  And that is simply not true.  However, when we start to deal with very large amounts of statements, then we can generally look away from this issue.

 

EXAMPLES

For each of the following functions, approximate the number of statements executed when the function is called.

 

Example 1 – Constant

 

public static int pyth(int a, int b)

{

   int a2 = a * a;

   int b2 = b * b;

   int c2 = a2 + b2;

   int c = Math.sqrt(c2);

   return c;

}

 

Solution 1

 

There are five statements. 

 

Note:  The statement with the function call goes to another function that likely has 15 to 20 statements in it.  We won’t worry about this level of detail though.

 

Example 2 – Simple loop

 

     public static int numberOutter(int n)

     {

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

        {

           System.out.println(i);

        }

     }

 

Solution 2

 

Calculating the number of statements here is a little more work.  First off, we have to deal with a loop.  Secondly, we have to express our answer in terms of n.  We have the following statements:

 

          1-Initialize i

          2-Test

          3-Output 0

          4-Update i

          5-Test

          6-Output 1
          7-Update i

          8-Test

 

          …

 

          ?-Output n-1

          ?-Update i

          ?-Test and break out

 

If you carefully count the statements, you should end up with 3n + 2 statements.

Also note that for a loop with c statements in it, the statement count would be 2n + cn + 2.

 

Example 3 – Nested Loops

 

     public static int lotsaNumbers(int n)

     {

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

        {

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

           {    

              System.out.println(i+k);
           }

        }

     }

 

Solution 3

 

This gets a little confusing.

 

Each pass in the interior loop ends up making about 3n+2 statements. 

If the interior loop had a different number of statements c in it, then the number of statements would be:

 

          2n + cn + 2

 

But since c is one, we have 3n + 2. 

 

The exterior loop can also be expressed by 2n + cn + 2 but with a value of c that is equal to 3n + 2.

 

So, the statements in the exterior loop could be approximated by using:

 

          2n + cn + 2 and subbing in c = 3n + 2


          = 2n + (3n + 2)(n) + 2

 

          = 2n + 3n2 + 2n + 2

 

          = 3n2 + 4n + 2

 

Therefore, there will be about 3n2 + 4n + 2 statements executed in this function.

Note that this equation is quite precise.  Really, it is too precise considering that not all statements are equal.  Therefore, when comparing different algorithms, instead of using a statement count method, we use the Big O Notation.

 

BIG O NOTATION

 

The Big O notation is used to approximate the complexity of an algorithm without trying to be exact.  Using this notation, we eliminate all less significant terms as well as any constant multipliers.

 

So, instead of saying 3n2 + 4n + 2, we will say simply n2.  We keep only the largest term and we remove the constant multipliers. 

Why do we do this?

 

First off, it is important to note that not all statements are equal.  So there is already error in a precise equation such as 3n2 + 4n + 2.  (Of note, any output statement is really a function call that includes hundreds of other lines.)

 

Second off, we are interested on how much computation will be required when the value of n is very large.  And in such cases, the value of the largest term is much more significant than for the other terms.

 

EXAMPLES

Simplify the following Big O notation problems.

 

#

PROBLEM

SOLUTION

EXPLANATION

A)

O(n+5)

O(n)

We remove all lesser terms.

B)

O(3n)

O(n)

We remove all multipliers.

C)

O(2n + 3)

O(n)

We remove all lesser terms and multipliers.

D)

O(n2 + n)

O(n2)

We remove all lesser terms.

E)

O(n3 + 3n2 + 2n – 8)

O(n3)

We remove all lesser terms.

F)

O(12n2 + n4)

O(n4)

We remove all lesser terms.

H)

O(n/2)

O(n)

We remove all multipliers.

I)

O(7)

O(1)

We remove all multipliers.  (7 x n0)

 

WHAT DOES THIS MEAN?

 

The simplified Big O notation gives a suggestion as to the growth of the number of statements with respect to the growth of the value n.

 

All functions that are O(n) will grow in a linear way.  All functions that are O(n2) grown in a quadratic way.

 

Note that when n is large enough, any function that is O(n2) will be much slower than a function that in O(n).

 

EASY TO USE

 

Once you understand the Big O notation, it is very easy to use to express the complexity of an algorithm because we no longer care about individual statements.  So it’s very fast to do.