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).

img

In Big O notation, we always use the worst case scenario for our calculations.

Some little tidbits

Drop the constants

If you have an algorithm described as O(2n), drop the 2 so it’s just O(n).

Drop the non-dominant terms

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!