1
$\begingroup$

I have a quick question about simplifying these exponents and then comparing them:

$8^{\log_2 n}, 2^{3log_2(log_2n)}$ and $2^{(log_2(n))^2} $

I know the third one evaluates to $n^{log_2(n)}$, but I'm not sure how I would simplify the other two. I do know that $2^{log_2(n)}$ = n, but how could I use this to simplify the other ones because I don't think I'm simplifying them correctly. I also tried simplifying 8 into $2^3$, but I wasn't sure what to do from there.

Thanks!

$\endgroup$
  • $\begingroup$ The result depends on $n$. $\endgroup$ – Michael Rozenberg Oct 7 '18 at 15:43
1
$\begingroup$

$$8^{\log_2n}=2^{3\log_2n}=(2^{\log_2n})^3=n^3$$ $$2^{3\log_2\log_2n}=(2^{\log_2\log_2n})^3=(\log_2n)^3$$ Comparing these with $n^{\log_2n}$ we see that asymptotically $$2^{3\log_2\log_2n}<8^{\log_2n}<2^{(\log_2n)^2}$$

$\endgroup$
1
$\begingroup$

The only formula you have to know is that, $\forall a > 0$, $x \in \mathbb{R}$, $$a^x = e^{x \ln(a)}$$

Therefore, you have $$8^{\log_2(n)}=e^{\log_2(n) \ln(8)} = e^{3 \ln(2) \frac{\ln(n)}{\ln(2)}} = e^{3 \ln(n)} = n^3$$

Similarly, you have $$2^{3\log_2(\log_2(n))} = e^{3\log_2(\log_2(n)) \ln(2)} = e^{3\ln(\log_2(n))} = (\log_2(n))^3$$

And finally $$2^{(\log_2(n))^2} = e^{(\log_2(n))^2 \ln(2)} = e^{\log_2(n) \ln(n)} = n^{\log_2(n)}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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