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


closed as off-topic by David Richerby, Evil, Yuval Filmus, Kyle Jones, Rick Decker Jan 31 '18 at 1:24

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about computer science, within the scope defined in the help center." – David Richerby, Evil, Yuval Filmus, Kyle Jones, Rick Decker
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ This seems to be a question about pure mathematics, not computer science. $\endgroup$ – David Richerby Jan 9 '18 at 18:09

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}. $$

  • $\begingroup$ Another way of seeing this that I find easier to understand is to use the identities $2^{a \cdot b} = (2^a)^b$ and $x = 2^{\log_2(x)}$: $3^{\log_2 n} = 2^{\log_2(3^{\log_2 n})} = 2^{{\log_2 n} \cdot \log_2(3)} = (2^{\log_2 n})^{\log_2(3)} = n^{\log_2 3}$. $\endgroup$ – holf Jan 9 '18 at 16:19

We will use the following facts:

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


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


Not the answer you're looking for? Browse other questions tagged or ask your own question.