Recurrence Relation $T(n) = T(\frac{n}{2}) + \sqrt{n}$

Question

$T(n) = T(\frac{n}{2}) + \sqrt{n}$ and $T(1) = 1$. Assume $n = 2^k$.

$$T(2^k) = T(2^{k-1}) + 2^{k/2}$$ $$T(2^{k-1}) = T(2^{k-1}) + 2^{k/4}$$ ... $$T(2) = T(1) + 2^{k/k} $$ $$T(1) = 1$$

I'm just really confused about how to go about finishing this. Any help would be appreciated!

Answer 1

$$ T(2^k) = T(2^{k-1}) + 2^{\frac{k}{2}} = T(2^{k - 2}) + 2^{\frac{k}{2}} + 2^{\frac{k-1}{2}} = T(2^{k-j}) + \sum_{m=0}^{j-1}{2^{\frac{k-m}{2}}} $$

Let $j = k$.

$$ T(2^k) = T(1) + \sum_{m=0}^{k-1}{2^{\frac{k-m}{2}}} = T(1) + \frac{2(1-2^{\frac{k}{2}})}{\sqrt{2} - 2}. $$

Answer 2

It's strange to say "assume $n = 2^k$" since $n$ is just a parameter to the function $T$. I would suggest the more unambiguous transform $S(k) = T(2^k)$. Then you get result that's easier to work with:

$$\begin{align} S(k) &= T\left(2^k\right) \\ &= T\left(\frac{2^k}2\right) + \sqrt{2^k} \\ &= T\left(2^{k-1}\right) + \sqrt{2}^k \\ &= S\left(k-1\right) + \sqrt{2}^k \end{align}$$

Now you can see that $S(k)$ is a geometric series, and $T(k) = S\left(\log_2\, k\right)$.