# How to analyze this recursion?

How can I analyze this recursion for $k>0$? $$T(n)=n+T\left(\frac{n}{2}\right)+T\left(\frac{n}{4}\right)+T\left(\frac{n}{8}\right)+\cdots+T\left(\frac{n}{2^k}\right)$$

I want to prove that $T(n)=\theta(n\log(n))$.

Is it true that $T(n)=n+\frac{n}{2}+\cdots+\frac{n}{2}=n+\frac{n}{2}\log(n)$?

I got it by iterations method of these:

\begin{align}T(n)&=n+T\left(\frac{n}{2}\right)+T\left(\frac{n}{4}\right)+T\left(\frac{n}{8}\right)+\cdots+T\left(\frac{n}{2^k}\right)\\ T\left(\frac{n}{2}\right)&=\frac{n}{2}+T\left(\frac{n}{4}\right)+T\left(\frac{n}{8}\right)+T\left(\frac{n}{16}\right)+\cdots+T\left(\frac{n}{2^{k+1}}\right)\\ T\left(\frac{n}{4}\right)&=\frac{n}{4}+T\left(\frac{n}{8}\right)+T\left(\frac{n}{16}\right)+T\left(\frac{n}{32}\right)+\cdots+T\left(\frac{n}{2^{k+2}}\right)\\ T\left(\frac{n}{8}\right)&=\frac{n}{8}+T\left(\frac{n}{16}\right)+T\left(\frac{n}{32}\right)+\cdots+T\left(\frac{n}{2^{k+3}}\right)\\ &\vdots\end{align}

• You're almost there. How many $\frac{n}{2}$'s do you have? One for each $T\left(\frac{n}{2^{k}}\right)$. But there are only logarithmically many of these since you only need to take this out until $2^k$ is larger than $n$. – Michael Burr Mar 28 '17 at 11:11
• @MichaelBurr $k$ is fixed here, for example, $k=42$. – Did Mar 28 '17 at 11:12
• @MichaelBurr log(n) , because $\frac{n}{2^k}=1$ --> k=log(n) ? but, how can i deal with the given that k is fixed? – user337036 Mar 28 '17 at 11:14
• I see, I misinterpreted your question. Thanks for the clarification. – Michael Burr Mar 28 '17 at 12:41
• This question also appeared at this MSE link. – Marko Riedel Mar 28 '17 at 21:16

We have $$T\left(\frac{n}{2}\right) = \frac{n}{2} + T\left(\frac{n}{4}\right) + \cdots + T\left(\frac{n}{2^{k+1}}\right) \tag{1}$$ and $$T\left(n\right) = n + T\left(\frac{n}{2}\right) + \cdots + T\left(\frac{n}{2^{k}}\right) \tag{2}$$ By $(2) - (1)$, we have $$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{2} - T\left(\frac{n}{2^{k+1}}\right) \tag{3}$$ implying (if $T(n) \geq 0$ for all $n$) $$T(n) \leq 2T\left(\frac{n}{2}\right) + \frac{n}{2}$$Thus by master theorem, $$T(n) = \mathcal{O}(n \log n)$$
We can not conclude $T(n) = \Omega(n \log n)$ if $k$ is fixed. As a counterexample, when $k = 1$, we have $$T(n) = T\left(\frac{n}{2}\right) + n$$ and in this case, $T(n) = \Theta(n)$.
• thank you, and how can you prove that $T(n)=Ω(nlog(n))$ while $k=log(n)$? – user337036 Mar 28 '17 at 11:34
• @Mathing I assume the logarithm base is $2$. Then $$T\left(\frac{n}{2^{k+1}}\right) = T\left(\frac{1}{2}\right)$$ which is a constant. Then you can apply the master theorem for equation $(3)$ immediately. – PSPACEhard Mar 28 '17 at 11:42