# Algebraic manipulation

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.

• Is $\lg$ the base 2 logarithm? If so ask yourself what $2^(\lg(n))$ is. – Henrik Jan 14 '15 at 18:01
• @Henrik $2^{\lg(n)}$ (you forgot the {} in latex).. – Loreno Heer Jan 14 '15 at 18:02
• Also remember that $\sqrt{n} = n^{\frac12}$ – Henrik Jan 14 '15 at 18:03
• @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. – BubbleTree Jan 14 '15 at 18:07

The solution is simple, $m = \log_2 n \implies 2^m = n \implies 2^{m/2} = n^{1/2} = \sqrt{n}$.