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)

  • 0
    In math mode use `\log` instead of `log` (similarly, `\sin` instead of `sin`, etc) and use `\left( \right)` instead of `()` so that the parentheses are stretched to be as large as the stuff enclosed.2012-05-08
  • 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}$$