Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
In math mode use \log instead of log (similarly, \sin instead of sin, etc) and use \left( \right) instead of () so that the parentheses are stretched to be as large as the stuff enclosed. – user17762 May 8 '12 at 21:43
I'll keep that in mind. Thanks! – user26649 May 8 '12 at 21:46
up vote 9 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.