Understanding Big O and O(log n)

This is a 2 min read

There are dozens of explanations if not hundreds about the Big O or Asymptotic notation. Here are some of the best written posts about it.

While you might have understood all the concepts clearly from the above posts like O(1), O(n) and o(n²). I wanted to clarify only one thing. What it means when some one says  O(log n). There are enough explanations out there for this too. But log can be ambiguous term. See what Donald Knuth has to say about it in his book “Concrete Mathematics”.

Three different notations for logarithms have been used in this chapter: lg, In, and log. We often use ‘lg’ in connection with computer methods, because binary logarithms are often relevant in such cases; and we often use ‘In in purely mathematical calculations, since the formulas for natural logarithms are nice and simple. But what about ‘log’? Isn’t this the “common” base-10 logarithm that students learn in high school-the “common” logarithm that turns out to be very uncommon in mathematics and computer science? Yes; and many mathematicians confuse the issue by using ‘log’ to stand for natural logarithms or binary logarithms. There is no universal agreement here. But we can usually breathe a sigh of relief when a logarithm appears inside O-notation, because 0 ignores multiplicative constants. There is no difference between O(lgn), O(lnn), and O(logn), as n -> infinity  similarly, there is no difference between 0 (Ig lg n), 0 (In In n), and O(loglog n). We get to choose whichever we please; and the one with ‘log’ seems friendlier because it is more pronounceable. Therefore we generally use ‘log’ in all contexts where it improves readability without introducing ambiguity.”

Actually in the algorithmic sense the log used in Big O are log2 n  or Binary logarithm. Lets do a pen and paper example to understand this.
As per wiki ,

x=\log_2 n \quad\Longleftrightarrow\quad 2^x=n.


Not to confuse you but there are 2 other animals Big Theta and Big Omega ;-), Don’t bother reading if you don’t want to confuse yourself here it is though