6

Are $\log_{10}(x)$ and $\log_{2}(x)$ in the same big-O class of functions? In other words, can one say that $\log_{10}(x)=O(\log x)$ and $\log_{2}(x)=O(\log x)$?

Dave Clarke
  • 20,205
  • 4
  • 68
  • 113
David Faux
  • 1,597
  • 5
  • 21
  • 28

2 Answers2

13

Yes. Because they differ only by a constant factor. Remember high school math:

$\log_2 x = \dfrac{\log_{10} x}{\log_{10}2}$.

Dave Clarke
  • 20,205
  • 4
  • 68
  • 113
2

Why?

$2^{\log_2 x} = x$

$\log_{10}(2^{\log_2 x}) = \log_{10} x$

$\log_2 x(\log_{10}2) = \log_{10} x$ $(*)$

$\log_2 x = \dfrac{\log_{10} x}{\log_{10}2}$

QED.

$(*) \log x^y = y*\log x$

The Unfun Cat
  • 1,793
  • 2
  • 16
  • 29