Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$$\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|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
1  
I'll keep that in mind. Thanks! –  user26649 May 8 '12 at 21:46

1 Answer 1

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|improve this answer

Your Answer

 
discard

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