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)$?
1
-
$\begingroup$ And x^$log(y)$ = y^$log(x)$. Magic. $\endgroup$ – The Unfun Cat Oct 9 '12 at 11:26
Add a comment
|
$\begingroup$
$\endgroup$
Yes. Because they differ only by a constant factor. Remember high school math:
$\log_2 x = \dfrac{\log_{10} x}{\log_{10}2}$.
$\begingroup$
$\endgroup$
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$