0

Recurrence of $T\left(n\right)=\:T\left(\frac{n}{2}\right)+n$ where T(1) = 1.

I know the Master Theorem is applicable here, but I have to prove it. I found a question similar to mine on this forum, but I didn't really understand the answer given. I should have a O(n) complexity from what I can tell from the Master Theorem.

I can see that $T\left(n\right)=\:T\left(\frac{n}{8}\right)+\frac{n}{4}+\frac{n}{2}+n$ so I'll have $T\left(n\right)=T\left(\frac{n}{2^k}\right)+\frac{n}{2^{k-1}}+\frac{n}{2^{k-2}}+...\:+n$ and that I can say that $n=2^k$ and get another sum from there, but I still don't understand how that gives me O(n) recurrence.

MikhaelM
  • 1,473

1 Answers1

2

I assume what you mean is that $$ \begin{align} T(2^k)&=T(2^{k-1})+2^k\\ &=T(2^{k-2})+2^{k-1}+2^k\\ &=...\\ &=T(1)+2+2^2+...+2^k\\ &=1+2+2^2+...+2^k\\ &=(1+2+2^2+...+2^k)\cdot(2-1)\\ &=(2+2^2+...+2^{k+1})-(1+2+2^2-...+2^k)\\ &=2^{k+1}-1 \end{align} $$ so for $n=2^k$ we have $T(n)=2n-1$ which is clearly $O(n)$.

String
  • 18,395