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.