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.