1
$\begingroup$

Im dealing with an equation of the form:

$$T(n)=2T(\sqrt n)+\log n$$

Letting $m=\log n$ we have:

$$T(2^m)=2T(2^{m/2}) + m$$

How did we go from $\sqrt n$ to $2^{m/2}$?

Taking into consideration that $2^m = 2^{\log n}$, I know that $\sqrt n = \sqrt 2^{\log(n)}$ but that wouldn't get rid of the square root or give us $m/2$ as an exponent.

$\endgroup$
  • $\begingroup$ Is $\lg$ the base 2 logarithm? If so ask yourself what $2^(\lg(n))$ is. $\endgroup$ – Henrik Jan 14 '15 at 18:01
  • 1
    $\begingroup$ @Henrik $2^{\lg(n)}$ (you forgot the {} in latex).. $\endgroup$ – Loreno Heer Jan 14 '15 at 18:02
  • 1
    $\begingroup$ Also remember that $\sqrt{n} = n^{\frac12}$ $\endgroup$ – Henrik Jan 14 '15 at 18:03
  • $\begingroup$ @Henrik, it would be n itself. Which is what i said with how sqrt(n) is just sqrt(2^m). Edit: just read your second part...okay that was dumb of me. I get it now. $\endgroup$ – BubbleTree Jan 14 '15 at 18:07
1
$\begingroup$

The solution is simple, $m = \log_2 n \implies 2^m = n \implies 2^{m/2} = n^{1/2} = \sqrt{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.