Help with recurrence $T(n) = T(n/2) + n$

Question

I just need help seeing where I went wrong in this solution.

$$T(n) = T\left(\frac{n}{2}\right) + n,~~~ T(1) = 0$$

By master theorem, this is $\theta(n)$.

However, when I try to solve it, it doesn't come out right. Where is my logic error?

$$T(n) = T\left(\frac{n}{2}\right) + n$$ $$T(n) = T\left(\frac{n}{4}\right) + n + n$$ $$T(n) = T\left(\frac{n}{8}\right) + n + n + n$$ $$T(n) = T\left(\frac{n}{16}\right) + n + n + n$$ Thus, the pattern appears to be: $$T(n) = T\left(\frac{n}{2^k}\right) + kn,~~~ k>0$$

If we assume $n = 2^k$, $$T(n)=T\left(\frac{n}{n}\right)+kn$$ $$T(n)=T\left(1\right)+kn$$ $$T(n)=0+kn$$ $$T(n)=kn$$

$k = \log_2 n$, so this can be rewritten as: $$T(n) = n \log_2(n)$$ However, this is incorrect. Where did I go wrong?

Thanks!

Answer 1

Hint:

$$T(n) = T\left(\frac{n}{2}\right) + n$$ $$T(n) = T\left(\frac{n}{4}\right) + \frac{n}{2} + n$$

Answer 2

Actually, because it is a recurring sequence, you get: $$T(n) = T\left(\frac{n}{2}\right) + n$$ $$T(\frac{n}{2}) = T\left(\frac{\frac{n}{2}}{2}\right) + \frac{n}{2}=T\left(\frac{n}{4}\right)+\frac{n}{2}$$ And so on: $$T(n) = T\left(\frac{n}{2}\right) + n$$ $$T(n) = T\left(\frac{n}{4}\right)+\frac{n}{2} + n$$ $$T(n) = T\left(\frac{n}{8}\right)+\frac{n}{4}+\frac{n}{2} + n$$ As you noticed the pattern, we do the same here: $$T(n) = T\left(\frac{n}{2^k}\right)+\sum_{j=0}^{k-1} \frac{n}{2^j},~~~k>0$$ As per your assumption $n=2^k$, we have: $$T(n)=T\left(\frac{n}{n}\right)+\sum_{j=0}^{k-1} \frac{n}{2^j}$$ $$T(n)=T\left(1\right)+\sum_{j=0}^{k-1} \frac{n}{2^j}$$ $$T(n)=0+\sum_{j=0}^{k-1} \frac{n}{2^j}$$ $$T(n)=n*\sum_{j=0}^{k-1} \frac{2^k}{2^j}$$ As you mentioned, $k=\log_2 n$: $$T(n)=n*\sum_{j=0}^{\log_2 n-1} \frac{2^{\log_2 n}}{2^j}$$ Simplify the logarithm: $$T(n)=n*\sum_{j=0}^{\log_2 n-1} \frac{n}{2^j}$$