Big O / Logarithmic Equivalency In one of the algorithms textbooks I was reading, it states that $O(3^{\log_2n})$ can be rewritten as $O(n^{\log_23})$. Why is this the case?

Recall the following log rule:

> $$\log_2 (x^k) = (k)(\log_2 x) \tag{1}$$

Now to prove that $3^{\log_2 n} = n^{\log_2 3}$, it suffices to prove that their logs (base $2$) are equal. Indeed, observe that: \begin{align*} \log_2(3^{\log_2 n}) &= (\log_2 n)(\log_2 3) &\text{by (1), where $x = 3$ and $k = \log_2 n$} \\\ &= (\log_2 3)(\log_2 n) &\text{by the commutativity of multiplication} \\\ &= \log_2(n^{\log_2 3}) &\text{by (1), where $x = n$ and $k = \log_2 3$} \\\ \end{align*} as desired. $~~\blacksquare$