0

$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!

user136038
  • 103

2 Answers2

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}. $$

  • @user136038 If you need more description feel free to let me know. Particularly, if a certain step confuses you, indicate it. –  Sep 25 '14 at 03:35
  • Hey! I just got back here. I'm confused about the summation part... where is the j-1 coming from in the summation? Couldn't we also put "to k-1" instead? – user136038 Sep 25 '14 at 05:31
  • @user136038 No we can't. Notice that on the step before, we have everything in terms of k. But as we iterate, we get $T(2^{k-3}), T(2^{k-4}), \ldots, T(2^{k-j})$ where $j$ represents how far we have expanded downwards. What using j allows us to do is define how many times we have replaced T with a value closer to our initial T. Do you see how this is happening? $T(n)$ is in terms of $T(n/2)$, so it's in terms of a smaller T. $j$ is how many smaller $T$'s, we have replaced. –  Sep 25 '14 at 05:45
  • And of course, every time we replace a T, we also need to include the $2^{\frac{k-j}{2}}$ term, as the formula is $T(n) = T(n/2) + n $. $n$ is the $2^{\frac{k-j}{2}}$ term here. That's what builds the summation. –  Sep 25 '14 at 05:48
  • $$T(2^{k-1}) + 2^{\frac{k}{2}}, j = 1$$ $$T(2^{k-2}) + 2^{\frac{k}{2}} + 2^{\frac{k-1}{2}}, j = 2$$ –  Sep 25 '14 at 05:54
0

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)$.

DanielV
  • 23,556