2
$\begingroup$

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}

$\endgroup$
5
  • 1
    $\begingroup$ 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$. $\endgroup$ – Michael Burr Mar 28 '17 at 11:11
  • $\begingroup$ @MichaelBurr $k$ is fixed here, for example, $k=42$. $\endgroup$ – Did Mar 28 '17 at 11:12
  • $\begingroup$ @MichaelBurr log(n) , because $\frac{n}{2^k}=1$ --> k=log(n) ? but, how can i deal with the given that k is fixed? $\endgroup$ – user337036 Mar 28 '17 at 11:14
  • $\begingroup$ I see, I misinterpreted your question. Thanks for the clarification. $\endgroup$ – Michael Burr Mar 28 '17 at 12:41
  • $\begingroup$ This question also appeared at this MSE link. $\endgroup$ – Marko Riedel Mar 28 '17 at 21:16
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ thank you, and how can you prove that $T(n)=Ω(nlog(n))$ while $k=log(n)$? $\endgroup$ – user337036 Mar 28 '17 at 11:34
  • 1
    $\begingroup$ @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. $\endgroup$ – PSPACEhard Mar 28 '17 at 11:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy