# Big O notation explained with examples

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.