Why is $3^{\log_2 n}$ the same as $n^{\log_2 3}$?
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}.
$$