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.