Omitting Bases in Logs in Big O

randerson112358
4 min readApr 4, 2018

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.

--

--