Search code examples
big-oasymptotic-complexity

Do log bases matter in Big O domination?

Given two functions:

f(n)=O(log2n) and g(n)=O(log10n)

Does one of these dominate the other?

Solution

  • No.

    The difference between bases is a difference by a constant, and constants are not considered in asymptotic efficiency.

    In this case, f(n) = O(g(n)) = O(lg(n)) In fact, f(n) = Θ(g(n)) = Θ(lg(n))