Big O notation is a way of roughly describing a functions efficiency over a large range of input parameters.

It allows developers to get a clear idea of how their algorithms will perform without including external factors such as CPU speed and current load.

int loopingAddition(int n) {
    int output = 0;

    for (int i = 0; i < n; i++) {
        output ++;
    }

    return output;
}

How will the above function perform when n gets really big? With each increase of n the cost will go up by 1 loop. Therefore this function scales exactly proportionally to the parameter passed in.

The above function in big O form would be O(n). The cost scales proportionally to n.

So how do you roughly describe an algorithm? How do you convert an algorithm to its Big O notation? To put it simply; remove the parts which have less affect when the value gets large. Lets say in the previous function we add another fixed loop before returning:

int loopingAddition(int n) {
    int output = 0;

    for (int i = 0; i < n; i++) {
        output ++;
    }

    for (int i = 0; i < 10; i++) {
        output ++;
    }

    return output;
}

If we do loopingAddition(10) the second loop will double the time taken. A considerable affect to the performance.

If we do loopingAddition(10000000) the second loop will have a negligible effect. We ignore any parts of the algorithm that do not have a relationship with n (the input).

Thus O(n) would be the big O notation of both the previous two functions and not O(n+10).

What is the big O notation of this function? :

int[] calculateSquares(int n) {
   int[n] squares;    

   for (int x = 0; x < n; x++) {
       for (int y = 0; y < n; y++) {
           squares[n] = y * x;
       }
   }
   return squares;
}

It creates an array of ints that are the squares up to the value specified. The number of loops is n^2.

The Big O notation is therefore simply O(n^2).

So far we’ve come across 2 classes of functions:

O(n) – linear time
O(n^2) – quadratic time

Almost all functions can be can be divided into several Big O forms (ordered by efficiency) :

1. O(1) – constant time; the calculation is performed in one step

2. O(log n) – logarithmic time; binary search is the classic example although steep at first the performance levels off allowing you to compute n for theoretically any value

3. O(n) – linear time

4. O(n lg n) – sublinear functions; sorting algorithms come under this class it’s a slightly steeper curve than linear time

5. O(n^2) – quadratic time

6. O(n^3) – cubic time; a steeper slow down than quadratic

7. O(C^n) – exponential time; an even steeper slow down (the recursive fibonacci sequence is an example of this)

8. O(n!) – factorial time – think of the cartesian product or an algorithm that calculates all possible permutations.

For a demonstration lets interpret the output of the Big O function as the time it takes to execute. For example lets say a unit of work costs 0.001 nanoseconds; O(1) == 0.001 nanoseconds. In practice this is completely unreliable – we don’t know the hardware that the algorithm is being executed on, we don’t know what the unit of work is – is it a loop, a DB call, a file transfer?

Ignoring that lets say each unit of work takes 0.001 nanoseconds the Big O class of functions perform as follows:

O(1) – any function with constant time will always be the same as the constant value in this case it will take 0.001 nanoseconds regardless of input
O(lg n) – with logarithmic time it takes 0.03 nano seconds for 1 billion values and will not change significantly as you approach infinity
O(n) – with linear time it progressively gets slower depending on input but even when n is 1 billion it will still take just 1 second to complete
O(n lg n) – with sublinear functions like mergesort or quicksort we still perform well when n is 10 million completing in 0.23 seconds. However when n == 1 billion we get a slowdown of 29.9 seconds.
O(n^2) – quadratic functions slow down when n approaches 100,000 at this point it takes 10 seconds to complete. For 1 billion a quadratic would take 31.7 years to complete
O(C^n) – exponential functions become useless when n > 30 taking around 1 second to complete when n is 30 and 13 days when n is 50
O(n!) – factorial functions are even worse and are only useful when n is 10 or less taking 77.1 years to complete when n == 20

The above hopes to give you a feel for each of the classes of Big O functions. Remember that the times above are completely useless in practice and depend on the unit of work, the time taken to do that work and any external factors.