$\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)
$\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)
$\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}$