The O() notation is an important concept for every Soft. Eng.

It is not only useful to pass coding interviews!

it’s the way we have to compare different processes (or algorithms) and speak about their efficiency (both in runtime and space.)

This is a https://abs.twimg.com/emoji/v2/... draggable="false" alt="🧵" title="Thread" aria-label="Emoji: Thread">thread about Big O https://abs.twimg.com/emoji/v2/... draggable="false" alt="👇" title="Rückhand Zeigefinger nach unten" aria-label="Emoji: Rückhand Zeigefinger nach unten">
The main feature of Big O: it’s a mathematical way of dealing with approximations.

When we say that an algorithm& #39;s runtime is O(n) we are saying that the time it takes for the code to finish is linearly correlated to the size of the input being processed (that& #39;s "n").

2/5
Linear Big O& #39;s are good. Every time you claim your code runs in O(n), you should be proud! https://abs.twimg.com/emoji/v2/... draggable="false" alt="🥳" title="Partying face" aria-label="Emoji: Partying face">

But you know what& #39;s even better? Constant time! https://abs.twimg.com/emoji/v2/... draggable="false" alt="‼️" title="Doppeltes Ausrufezeichen" aria-label="Emoji: Doppeltes Ausrufezeichen">

This one is represented as O(1): no matter how large is the input, your code will always take the same time to run.

3/5
Here are some examples of commonly known algorithms and their runtime in Big O:

https://abs.twimg.com/emoji/v2/... draggable="false" alt="▫️" title="Weißes kleines Quadrat" aria-label="Emoji: Weißes kleines Quadrat">O(1): Array access
https://abs.twimg.com/emoji/v2/... draggable="false" alt="▫️" title="Weißes kleines Quadrat" aria-label="Emoji: Weißes kleines Quadrat">O(ln n): Binary search
https://abs.twimg.com/emoji/v2/... draggable="false" alt="▫️" title="Weißes kleines Quadrat" aria-label="Emoji: Weißes kleines Quadrat">O(n): Sequential search
https://abs.twimg.com/emoji/v2/... draggable="false" alt="▫️" title="Weißes kleines Quadrat" aria-label="Emoji: Weißes kleines Quadrat">O(n lg n): Merge sort
https://abs.twimg.com/emoji/v2/... draggable="false" alt="▫️" title="Weißes kleines Quadrat" aria-label="Emoji: Weißes kleines Quadrat">O(n^2): Selection sort
https://abs.twimg.com/emoji/v2/... draggable="false" alt="▫️" title="Weißes kleines Quadrat" aria-label="Emoji: Weißes kleines Quadrat">O(c^n): Traveling Salesman

4/5
Mastering Big O Notation is not hard, and it will only take you doing some exercises to get a good handle of it.

And once you do, you’ll have a great way to compare and contrast different solutions to a problem!

5/5
You can follow @svpino.
Tip: mention @twtextapp on a Twitter thread with the keyword “unroll” to get a link to it.

Latest Threads Unrolled: