Logarithmic Bases and Complexity Theory

Why Logarithmic Bases Don’t Matter in Big O Notation

Let us say that you have an algorithm that requires \(log_{10} n\) steps to execute, where \(n\) is the size of the problem instance. (You don’t, obviously. The number 10 isn’t special in computer science.) Is its complexity best described as \(O(log_{10} n)\) ?

Consider the following pearl of wisdom:

\[log_{10}k = \frac{log_{2}k}{log_{2}10}\]

Now, \(log_{2}10 \approx \frac{1}{3}\) , which is a constant coefficient. These get dropped in Big O notation. Therefore, we should simplify our complexity statement from \(log_{10} n\) to \(log n\) .

The base 2 is implied. In computer science we like 2.