Member-only story

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.

Create an account to read the full story.

The author made this story available to Medium members only.
If you’re new to Medium, create a new account to read this story on us.

Or, continue in mobile web

Already have an account? Sign in

No responses yet

Write a response