4
$\begingroup$

$\mathcal{O} \left(3^{\log_2(n)} \right) = \mathcal{O} \left(n^{\log_2(3)} \right)$

Does anyone have any idea how the right side was arrived at? (The $\mathcal{O}$ is Big-$\mathcal{O}$ notation)

  • 1
    I'll keep that in mind. Thanks!2012-05-08

1 Answers 1

9

$\displaystyle3^{\log_2(n)} = \left(2^{\log_2(3)} \right)^{\log_2(n)} = 2^{\left(\log_2(3) \log_2(n)\right)} = 2^{\left(\log_2(n) \log_2(3) \right)} = \left(2^{\log_2(n)} \right)^{\log_2(3)} = n^{\log_2(3)}$ We have used the following facts in getting the above result. $a = b^{\log_b(a)}$ $\displaystyle \left(x^r \right)^s = x^{rs}$