Kirill Zonov

Brief introduction to complexity notations of algorithms (Big-O and other)

April 17, 2017 | 2 Minute Read

Currently I’m in process of reading a big book about algorithms. And there is a small thing I want to share. A lot of people has no clue what is the O(n) or O(log n). Just because they don’t need it right now, or skipper this lecture in University or whatever. But among those who know usually the big ”O” is the only thing they know. But actually there are some more complexity notations and I’m going to share some brief information about them. Actually there are four different notations: Big-O, Small-O, Big-Omega, Small-Omega, Theta.

  1. Big-O. F.e. if complexity of some algorithm is a O(n) it means that it's execution time will raise not faster than linear function (maybe with some constant). So we can write O(cn), where c - is some constant, but actually no one is doing that just because it doesn't make sense in process of describing complexity. So for example for Quick Sort this Big-O is a O(n²). It means that if for sorting two elements your algorithm will take up to 4 milliseconds, for one hundred it will take up to 10 seconds.
  2. Small-O. Completely the same as Big-O, but with more strict condition, like < instead of ≤. So if algorithm complexity is a o(n²) it means that it's execution time will never raise as fast as n².
  3. Big-Omega. It's the opposite of Big-O. F.e. for Quick Sort Ω(n log n) is a complexity in the best case. It means that actually it can raise with just n * log(n) speed in the best case. In average not, but it's possible.
  4. Small-Omega. The same as with Small-O. It's just more strict condition. It looks like ω(n log(n)), if you are not familiar with greek alphabet enough.
  5. Theta. The last but not least is Theta. For Quick Sort average time is θ(n log(n)), so it means that in usual case it's execution time will raise as n * log(n) function. It doesn't have smth like small theta or big theta because wtf, it's will not make sense!

Now you know all five notations, but I’m pretty sure that knowing Big-O and Theta of the most popular algorithms will be enough for most live situations. F.e. if your wife will tell you to declutter your wardrobe and put your socks to one shelf and t-shirts to another - it’s just a O(n) complexity task, so you can be calm.