Omitting Bases in Logs in Big O
Why we do not consider base of log in time complexity
For asymptotic complexity, base of logarithms does not matter, but why ?
In this article I plan on answering that question.
First we must look at the definition of Big O. A function f(n) is said to belong to O(g(n)) if and only if f(n) ≤ C*g(n) whenever n >k , where both k and C are constants.
f(n) ≤ C*g(n) whenever n > k
Let’s show log base a of n is Big O of log base b of n, where a> 1 and b > 1. This means b could be any value like 5 , 7, or 89 etc., and same thing goes for a it could be 2,3, 90, or 7 etc.
In order to show this our f(n) = log base a of n and our g(n) = log base b of n. This would give us the following equation.
We can choose values for C and k that would make the above equation true. I will choose C = log base a of b and k = 0. Now our equation will look like the following.
Notice the right hand side of the equation (log base a of b times log base b of n). We can rewrite this equation thanks to the properties of logarithms.