Big 0 notation is notation used to describe how efficient an algorithm is. It’s incredibly important to know this since every major employer will question you on this.
A hierarchy of functions exist:
1 | log n | n, , | |
---|---|---|---|
Constant | Logarithm | Polynomial | Exponential |
Where the further right they are, the the longer take it takes. Big O notation uses these functions to describe algorithm efficiency. O(2^n) is larger than O(1).
In Big O notation, we always use the worst case scenario for our calculations.
If you have an algorithm described as O(2n), drop the 2 so it’s just O(n).
O(n^2 + n) just becomes O(n^2). Only keep the larger one in Big O.
If you have a special sum such as O(b^2 + a) you can’t drop either because without knowledge of what b and a are.
Bet you were expecting some hard to understand guide to Big O huh? Well, this is all it is. You just need to memorise (or learn) the hierarchy and then take some algorithms and find out what their Big O notation is. You should really practice this!