Why is $3^{\log_2 n}$ the same as $n^{\log_2 3}$? [closed]

Question

I am reading about divide and conquer algorithm at following link on page on 57 in this link. The document analyzes the running time of the algorithm. At the very top level, when $k = 0$, this works out to $O(n)$. At the bottom, when $k = \log_2 n$, it is $O(3^{\log_2 n})$, which, the author claims, can be rewritten as $O(n^{\log_2 3})$.

My question is:

Why can $O(3^{\log_2 n})$ be rewritten as $O(n^{\log_2 3})$?

Answer 1

The two expressions are equal: $3^{\log_2 n} = n^{\log_2 3}$. To see this, you can use the following identities: $\log_a b = \log_c b/\log_c a$, $\log_a b = 1/\log_b a$, and $a^{\log_a b} = b$. Using these identities, we get $$ 3^{\log_2 n} = 3^{\log_3 n / \log_3 2} = 3^{\log_3 n \cdot \log_2 3} = (3^{\log_3 n})^{\log_2 3} = n^{\log_2 3}. $$

Answer 2

We will use the following facts:

• $2^{\log_2 x}=x$; and
• $\log_2 x^y = y\log_2 x$.

So,

$$\begin{align} x=3^{\log_2 n} &= 2^{\log_2(3^{\log_2 n})}\\ &=2^{(\log_2 n)(\log_2 3)}\\ &=2^{y \log_2 n}\\ &=2^{\log_2 n^y}\\ &=2^{\log_2 (n^{\log_2 3})}\\ &=n^{\log_2 3}.\end{align}$$