Big O notation
Tags: computerscience, algorithms, performance
Published: 2020-12-29 16:34:06

We all know how to code. We may know how to make "clean code", or at least we though about what makes the code clean (Uncle Bob definitely has). But what about performance? How can we anticipate whether the algorithm is fast and memory efficient? How can we analyze algorithm and compare one to another? Turns out, the Big O notation is there just for that!

In short, the efficiency of an algorithm is the number of steps your code takes to execute a task.
 
For example, if we were to create a function that displays its input, for one one string, we'll do one action, for an array of 100, we'll do 100 prints and for {%katex inline%}n{%endkatex%} we'll do {%katex inline%}n{%endkatex%}. We can note that {%katex inline%}O(n){%endkatex%} or "Big O of {%katex inline%}n{%endkatex%}".

If however the number of action we take does not depend of the input, such as accessing the {%katex inline%}n^{th}{%endkatex%} item of an array (which will always just be one action, regardless the size of the array), your algorithm will run in constant time, thus can just be written {%katex inline%}O(1){%endkatex%}.
We are not necessarily interested in the actual precision and the actual numbers of steps nor the actual time it would take to run the code given an input, but by its magnitude. We actually are comparing if {%katex inline%}O(log_2n){%endkatex%} is better or worse than {%katex inline%}O(n²){%endkatex%}.

If we actually were to look at the actual complexity of the `print` function, which we assumed to work in {%katex inline%}O(1){%endkatex%}, we'd be quite wrong. The print function takes a string as a parameter to log it in the console. The print function is most likely to use the POSIX `write` function, which is a system call to dump a certain amount of data into a file descriptor (which is the representation of a file or the terminal etc...). In our case, the data would be a string which basically is an array of char. Knowing the length of the string implies going from the beginning of the string to the null character (i.e. `\0`) which is {%katex inline%}O(n){%endkatex%}. Going from one char to another implies incrementing a variable (which has a computational cost {%katex inline%}t_{add}{%endkatex%}) that we need to do only once. We also need to check the value of the current char which has the computation cost of {%katex inline%}t_{check}{%endkatex%} as well as the jump (loop) which has the computation cost of {%katex inline%}t_{jump}{%endkatex%}. The actual computational cost of moving from the first character of a string is actually {%katex inline%}O \left( n \cdot (t_{inc} + t_{check} + t_{jump})\right){%endkatex%}. And that's just without having a function which we'd call and returns a value: `while(str[i++]);`.

What gives the insight of the efficiency of the algorithm is {%katex inline%}n{%endkatex%}, not the constants. In the long run, {%katex inline%}100n{%endkatex%} will always be better than {%katex inline%}\frac{n^2}{2}{%endkatex%}. In that regard, we can always drop the non-deterministic factors, {%katex inline%}O(n){%endkatex%} instead of {%katex inline%}O(100n){%endkatex%} and {%katex inline%}O(n^2){%endkatex%} instead of {%katex inline%}O(\frac{n^2}{2}){%endkatex%}. 

---

# Practice: The egg drop problem

> We have two eggs and a 100 stories building. At which floors will the eggs break?

Both are strictly identical. One can throw the egg by a window an infinity of time, if it didn't break the first time, it won't. EVER. On this floor and those bellow. EVER.There is a real scientific relevance in performing this test and knowing its result.We have a teleport machine which allows us to access each floor instantly.

## With just one egg...

The solution with two eggs is not that easy. Let's start to solve with one first. Intuitively, we'd go from the ground and try each floors until it breaks. Which means:
best case scenario: we do one throw, on the ground floor
worst case scenario: the egg breaks at the 100th floor...
With that procedure, if we had a 1,000 stories building we would do 1,000 throws at worse. And with a {%katex inline%}n{%endkatex%} stories building, {%katex inline%}n{%endkatex%} throw.
This approach is in {%katex inline%}O(n){%endkatex%}

## With an infinity of eggs...

This is the most intuitive approach, the one most people go with.

You start at floor 50. If the egg breaks, you go to floor 25. If it didn't break then, to floor 38 (depending on how you round), etc... That is, you split the building in two and try at the middle. For each iteration you split in two the upper remaining half if the egg didn't break, and the lower remaining half if it did.

If we take a 32 story building, we would tests 16, 8, 4, 2 and finally one:
- {%katex inline%}16 = \frac{32}{2^1}{%endkatex%}
- {%katex inline%}8 = \frac{32}{2^2}{%endkatex%}
- {%katex inline%}4 = \frac{32}{2^3}{%endkatex%}
- {%katex inline%}2 = \frac{32}{2^4}{%endkatex%}
- and finally {%katex inline%}1 = \frac{32}{2^5}{%endkatex%}.
That is: {%katex inline%}1 = \frac{n}{2^x} \Leftrightarrow x = \log_2{n}{%endkatex%}

> How does one go from {%katex inline%}\frac{n}{2^x} to \log_2{n}{%endkatex%}?
    
The first thing to know about log is:
   
{%katex%}
\textcolor{blue}{base}^{\textcolor{red}{a}} = \textcolor{green}{b}
\Leftrightarrow \log_{\textcolor{blue}{base}}{\textcolor{green}{b}}
= \textcolor{red}{a}
\\\ \text{so in our case}:
\\\ \frac{\textcolor{green}{n}}{\textcolor{blue}{2}^{\textcolor{red}{x}}}= 1
\Leftrightarrow \textcolor{green}{n}
= \textcolor{blue}{2}^{\textcolor{red}{x}}
\Leftrightarrow \log_{\textcolor{blue}{2}}{\textcolor{green}{n}}
= \textcolor{red}{x}
{%endkatex%}

> Why when I do {%katex inline%}\log{(4)}{%endkatex%} I get {%katex inline%}\approx 1.39{%endkatex%} and not 2?

One must keep in mind that our numeric system is in base 10, so {%katex inline%}\log{%endkatex%} in most calculators are also in base 10 ({%katex inline%}\log_{10}{%endkatex%}). However, we are in base 2. Not because computers are binary, but because we split the building in two, thus making two branches, and each iterations we make two more branches. In order to go from one to another we need to know this:
    
{%katex%}
\begin{aligned}
    \log_{\color{red}{base}}{x}
    & = {\log_{\color{blue}{otherbase}}{x}
      \over
      \log_{\color{blue}{otherbase}}{\color{red}{base}}
    }
\\\ \Rightarrow \log_{\color{red}{2}}{x}
    & = {\log_{\color{blue}{10}}{x} \over \log_{\color{blue}{10}}{\color{red}{2}}}
\end{aligned}
{%endkatex%}

The complexity would then be {%katex inline%}O(\log_2{n}){%endkatex%}.

For a 100 stories building we'd have {%katex inline%}\approx{%endkatex%} 7 throws,
For a 1000 stories build we'd have {%katex inline%}\approx{%endkatex%} 10
That is way better than our previous try. However, we don't have an infinity amount of eggs, but two.

## Back to two eggs...

We need an approach that's a bit a mix of both.
If we split the building in equal chunks, and try the top of each chunk, we'd know that if the egg breaks we have to try each floor of that chunk and that'd work with two eggs. 10 chunks seems an attractive number, but before using that, let's make sure it's the proper one.

We want a balance between the number of floor we'd try and the number of chunks, that is, the number of chunks must be equal to the number of floors in that chunk:

{%katex%}
\begin{aligned}
  floors \cdot chunks & = building \\\ 
  \Rightarrow chunks \cdot chunks & = building \\\ 
  \Leftrightarrow chunks^2 & = building \\\ 
  \Leftrightarrow chunks & = \sqrt{building}
\end{aligned}
{%endkatex%}

Which in our case is 10, lucky.Now our worst case, would be floor 99, because we'd have to test floors 10, 20, ..., 80, 90, 100 and then 91, 92, ..., 98, 99. That is 19 tests.
Now the complexity is not really surprising: {%katex inline%}O(2\sqrt{n}){%endkatex%}, and dropping the constants {%katex inline%}O(\sqrt{n}){%endkatex%}

## Is there better?

In the worst case scenario we'll do 19 tests, as we just saw. But if the floor is 13, we'd have done 6 tests: 10, 20, 11, 12, 13, 14. Perhaps we can redistribute the floors in the chunks so that, regardless of the floor, we're guaranteed to do the same amounts of tests.

In other words, for each chunk that has passed, we test one less floor. For example, if the first chunk is 10, the next will be 9 and the next 8 and so on. That way, if it breaks at 9, we'll test 10, 1, 2, 3, ..., 8, 9 (10 tests), if it breaks at 18, we'll test 10, 19, 11, 12, ..., 17, 18 (10 tests) and so on.

So basically we need to resolve {%katex inline%}k + ... + 3 + 2 + 1 = building{%endkatex%} and figure {%katex inline%}k{%endkatex%} out. And that's {%katex inline%}building = \frac{n(n+1)}{2}{%endkatex%}:

{%katex%}
\begin{aligned}
1 + 2 + 3 + 4 + 5 + 6 & = (1 + 6) + (2 + 5) + (3 + 4)
\\\ & = (s_0 + s_n) + (s_1 + s_{n - 1}) + (s_2 + s_{n - 2})
\\\ \text{and } (s_0 + s_n) &= (s_1 + s_{n - 1}) = (s_2 + s_{n - 2})
\\\ \Rightarrow 1 + 2 + ... + n & = (1 + n) + (1 + n) + (1 + n)
\\\ & = \frac{n}{2}(1 + n)
\end{aligned}
{%endkatex%}

In our case we want to resolve {%katex inline%}\frac{n(n + 1)}{2} = n \Leftrightarrow \frac{n^2}{2} + \frac{n}{2} - n = 0{%endkatex%}.

This is a quadratic equation: {%katex inline%}ax^2 + bx + c = 0{%endkatex%} that you should be able to solve
    
{%katex%}
\begin{aligned}
  ax^2 + bx + c & = 0
  \\\ ax^2 + bx & = -c
  \\\ x^2 + \frac{b}{a}x
    &= -\frac{c}{a}
    \mathit{\text{  we divide by a which is non 0}}
  \\\ x^2 + \frac{b}{a}x + \left(\frac{b}{2a}\right)^2
    &= -\frac{c}{a} + \left(\frac{b}{2a}\right)^2
    \mathit{\text{  which will help us refacto}}
  \\\ \left(x + \frac{b}{2a}\right)^2
    &= -\frac{c}{a} + \left(\frac{b}{2a}\right)^2
    \mathit{  \text{remember: } (a + b)^2 = a^2 + 2ab + b^2}
  \\\ \left(x + \frac{b}{2a}\right)^2
    &= -\frac{c}{a} + \frac{b^2}{4a^2}
  \\\ \left(x + \frac{b}{2a}\right)^2
    &= \frac{b^2 - 4ac}{4a^2}
  \\\ x + \frac{b}{2a}
    &= \pm \frac{\sqrt{b^2 - 4ac}}{2a}
  \\\ x &= \pm \frac{\sqrt{b^2 - 4ac}}{2a} - \frac{b}{2a}
  \\\ x &= \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}
    \mathit{\text{  this should be familiar}}
\end{aligned}
{%endkatex%}

In our case:

{%katex%}
\begin{aligned}
\frac{1}{2}n^2 + \frac{1}{2}n - 100 &= 0
  \\\ n &= {-\frac{1}{2} \pm \sqrt{\left(\frac{1}{2}\right)^2 - 4 \cdot \frac{1}{2} \cdot -100} \over 2 \cdot \frac{1}{2}} 
  \\\ n &= -\frac{1}{2} \pm \sqrt{\frac{1}{4} + 200}
  \\\ n &\approx 13.65
\end{aligned}
{%endkatex%}

That gives a complexity of {%katex inline%}O\left(\sqrt{\frac{1}{4} + 2n} - \frac{1}{2}\right){%endkatex%}, that is, for a 100 stories building, we would do at worst approx. 14 throws to find the right floor.

The complexity actually is {%katex inline%}O(\sqrt{n}){%endkatex%} which is the same as the previous algorithm we found. Let's compare the four:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/us436covfw7f6m5fp5ws.png)

red: with 1 egg: {%katex inline%}O(n){%endkatex%}
green: with an infinity of eggs: {%katex inline%}O(\log_2{n}){%endkatex%}
orange: our first 2 eggs solution: {%katex inline%}O(2\cdot\sqrt{n}){%endkatex%}
blue: our second 2 eggs solution: {%katex inline%}O\left(\sqrt{\frac{1}{4}+2n} - \frac{1}{2}\right){%endkatex%}
We can clearly see the difference between the {%katex inline%}O(n){%endkatex%}, {%katex inline%}O(\sqrt{n}){%endkatex%} and {%katex inline%}O(\log_2{n}){%endkatex%}, regardless of the constant we dropped. Of course, the constant make sense when comparing two algorithm of the same overall complexity (for 1600 floors, there is a 30 try offset between the 1st two eggs solution and the second).

---

# Going further...
Up until this point we've counted the number of steps. We call this the "time complexity" because it gives a sense of how long the algorithm will take to run.

The same logic can apply to the amount of memory the algorithm would take: "space complexity". In this case, you just need to count how many variable will need to be created. 

For example, if you want to count the number of unique entries in an array, your first bet would probably to use a Set. For each new entry, you'd check the Set if the entry exists and create it otherwise. This algorithm will run in {%katex inline%}O(n){%endkatex%} time (because you'd have to go through each entry) and {%katex inline%}O(n){%endkatex%} space because, worst case scenario, the array is full of unique item thus you create {%katex inline%}n{%endkatex%} new entry in the Set (A bloom filter would probably be an interesting alternative in {%katex inline%}O(n){%endkatex%} space and {%katex inline%}O(1){%endkatex%} space, but that would come with some false positive - we won't get into that now).

### But... there's more.

We don't have to only talk about the "worst case scenario" like we did during this article. The worst case scenario actually is the "asymptotic tight upper bound" of an algorithmic function, which means that this is exactly how wrong it will be if everything goes wrong.
For example, if you say "I'll arrive in 20mn, 1h if there's traffic", 1 hour is your upper bound. That's basically Big O. 20mn however is the "tight lower bound", or Big Omega: {%katex inline%}\Omega(n){%endkatex%}
You could have just said "I'll arrive to work before the end of the day", that would be a "loose upper bound", or little o {%katex inline%}o(n){%endkatex%}. But if you say "I'll arrive in an instant" would be a "loose lower bound" or little omega {%katex inline%}\omega(n){%endkatex%}.
If you know that'll you will arrive in 40mn, that would be the "expected average case scenario" or Big Theta {%katex inline%}\Theta(n){%endkatex%}. It is in fact the tight bound of the function, both upper and lower.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/8msc1ewaueyxwfeqpi82.png)

If we look at the graph, our algorithm {%katex inline%}f(n){%endkatex%} runs in {%katex inline%}\Theta(n){%endkatex%} and is bounded between {%katex inline%}O(n){%endkatex%} and {%katex inline%}\Omega(n){%endkatex%}. In the long run, we know it won't get worse than {%katex inline%}o(n^2){%endkatex%} nor better than {%katex inline%}\omega(\log{n}){%endkatex%}

### Common complexity

- {%katex inline%}O(1){%endkatex%}: direct access (e.g. in an array or a Hashmap / Set)
- {%katex inline%}O(n){%endkatex%}: looping through the input a constant amount of time (e.g. index lookup, counting)
- {%katex inline%}O(n^2){%endkatex%}: for each input, look at every other input (e.g. bubble sort)
- {%katex inline%}O(\log_2{n}){%endkatex%}: divide the problem (e.g. binary tree lookup)
- {%katex inline%}O(n\log{n}){%endkatex%}: sorting
- {%katex inline%}O(!n){%endkatex%}: combinatorics