I don't perfectly understand this concept, how would I go about calculating the big theta of $4^{\log_2(n)}$.

My instincts tell me this would end up as $\Theta(4^n)$, is that correct?

  • $\begingroup$ $4^{\log_2 n}=2^{2\log_2 n}=n^2$ because $b^{\log_b(n)}=n$ $\endgroup$ – kingW3 Jun 21 '18 at 18:40
  • $\begingroup$ Thank you, @kingW3, is the procedure this straight forward, no calcuating upper and lower bounds? $\endgroup$ – LukaTheLegend Jun 21 '18 at 18:47
  • 1
    $\begingroup$ They are telling you the function is literally the same thing as $n^2.$ So $\Theta(4^{\log_2(n)})$ is just a funny way of writing $\Theta(n^2).$ $\endgroup$ – spaceisdarkgreen Jun 21 '18 at 19:26

Your Answer

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

Browse other questions tagged or ask your own question.