3
$\begingroup$

I am trying to solve the recurrence below but I find myself stuck.

$T(n) = \frac{n}{2}T(\frac{n}{2}) + \log n$

I have tried coming up with a guess by drawing a recurrence tree. What I have found is

number of nodes at a level: $\frac{n}{2^{i}}$
running time at each node: $\log \frac{n}{2^{i}}$
total running time at each level: $\frac{n}{2^{i}} \log \frac{n}{2^{i}}$

I try to sum this over through n > $\log n$ which is the height of the tree

$\begin{align} \sum\limits_{i=0}^n \frac{n}{2^{i}} \log \frac{n}{2^{i}}&= n \sum\limits_{i=0}^n \frac{1}{2^{i}} \log \frac{n}{2^{i}}\\ &=n \sum\limits_{i=0}^n \frac{1}{2^{i}} (\log n - \log 2^{i})\\ &=n \sum\limits_{i=0}^n \frac{1}{2^{i}} \log n - \sum\limits_{i=0}^n \frac{1}{2^{i}} \log 2^{i}\\ &=n \sum\limits_{i=0}^n \frac{1}{2^{i}} \log n - \sum\limits_{i=0}^n \frac{ \log 2^{i}}{2^{i}}\\ &=n \sum\limits_{i=0}^n \frac{1}{2^{i}} \log n - d \sum\limits_{i=0}^n \frac{i}{2^{i}}\\ &=2 n \log n - d \sum\limits_{i=0}^n \frac{i}{2^{i}} \end{align}$

I am still trying to figure out the sum of the second summation above but I somehow feel that it will be bigger than $2n \log n$ which makes my whole approach wrong.

Is there another way to tackle this problem?

  • 6
    What if $n$ is odd? And what is $T(1)$?2012-01-25

3 Answers 3

5

Consider the equality $ 1+x+x^2+...+x^n=\frac{x^{n + 1} -1}{x-1} $ Differentiate it by $x$, then multiply by $x$: $ x+2x^2+3x^3+...+n x^n=\frac{nx^{n+2} - (n + 1)x^{n+1} + x}{(x-1)^2} $ Now we can substitute $x=\frac{1}{2}$ and obtain $ \sum\limits_{i=0}^n\frac{i}{2^i}=n\left(\frac{1}{2}\right)^{n} - (n + 1)\left(\frac{1}{2}\right)^{n-1} + 2 $

3

Summary: Like in several questions of the same ilk asked previously on the site, the recursion can only determine each $T(n)$ as a function of $T(2i+1)$ and $k\geqslant0$, where $n=(2i+1)2^k$. Furthermoree, the series considered by the OP are simply not relevant to the asymptotics of $T(n)$. The growth of $T(n)$ of the order of $n\log n$, which the OP seems to infer, is not compatible with the recursion at hand since, speaking very roughly, $T(n)$ grows like $n^{\frac12\log n}$.

Gory details: Consider for example $t_k=T(2^k)$. Then, for every $k\geqslant1$, $ t_k=2^{k-1}t_{k-1}+k\log2, $ hence the change of variables $ s_k=2^{-k(k-1)/2}t_k $ yields the recursion $s_0=t_0=T(1)$ and $ s_k=s_{k-1}+2^{-k(k-1)/2}k\log2$. This is solved by $ s_k=s_0+\log2\sum\limits_{i=1}^ki2^{-i(i-1)/2}, $ whose translation in terms of $t_k$ is $ t_k=2^{k(k-1)/2}\left(T(1)+\log2\sum\limits_{i=1}^k\frac{i}{2^{i(i-1)/2}}\right). $ Finally, $ T(2^k)=2^{k(k-1)/2}\tau_0-(\log2)\,(k/2^{k})+o(k/2^k),$ with $ \tau_0=T(1)+(\log2)\,\sum\limits_{i=1}^{\infty}\frac{i}{2^{i(i-1)/2}}= T(1)+1.69306\ldots $ Conclusion: One sees that, along the subsequence indexed by the powers of $2$, $T(n)$ grows roughly like $n^{\frac12\log n}$ rather than like $n\log n$. The same argument applies to each subsequence indexed by the powers of $2$ times any given odd integer.

3

The summation $ \sum\limits_{i=0}^n \frac{i}{2^{i}} $

is equal to $ \sum\limits_{i=0}^n i(\frac{1}{2})^i $

which is of the form $ \sum\limits_{i=0}^n ix^i, x = \frac{1}{2} $

Consider the summation $ \sum\limits_{i=0}^n x^i = \frac{x^{n+1} - 1}{x - 1} $

By differentiating with respect to $x$ we have $ \frac{d}{dx}\left( \sum\limits_{i=0}^n x^i \right) = \frac{d}{dx} \left( \frac{x^{n+1} - 1}{x - 1} \right)$ $ \Rightarrow \sum\limits_{i=0}^n ix^{i-1} = \frac{(x - 1)(n + 1)x^n - (x^{n+1} -1)(1)}{(x - 1)^2} $ $ \Rightarrow \sum\limits_{i=0}^n ix^{i-1} = \frac{(x^{n+1} - x^n)(n + 1) - x^{n+1} + 1}{(x - 1)^2} $ $ \Rightarrow \sum\limits_{i=0}^n ix^{i-1} = \frac{(nx^{n+1} - nx^n) + (x^{n+1} - x^n) - x^{n+1} + 1}{(x - 1)^2} $ $ \Rightarrow \sum\limits_{i=0}^n ix^{i-1} = \frac{nx^{n+1} - nx^n + x^{n+1} - x^n - x^{n+1} + 1}{(x - 1)^2} $ $ \Rightarrow \sum\limits_{i=0}^n ix^{i-1} = \frac{nx^{n+1} - nx^n - x^n + 1}{(x - 1)^2} $ By multiplying $x$ to both sides, $ x\sum\limits_{i=0}^n ix^{i-1} = x\left( \frac{nx^{n+1} - nx^n - x^n + 1}{(x - 1)^2} \right)$ $ \Rightarrow \sum\limits_{i=0}^n ix^{i} = \frac{nx^{n+2} - nx^{n+1} - x^{n+1} + x}{(x - 1)^2} $ By substitution $ \left( x = \frac{1}{2} \right) $, $ \sum\limits_{i=0}^n i\left(\frac{1}{2}\right)^{i} = \frac{n\left(\frac{1}{2}\right)^{n+2} - n\left(\frac{1}{2}\right)^{n+1} - \left(\frac{1}{2}\right)^{n+1} + \left(\frac{1}{2}\right)}{(\left(\frac{1}{2}\right) - 1)^2} $

$ \Rightarrow \sum\limits_{i=0}^n i\left(\frac{1}{2}\right)^{i} = \frac{n\left(\frac{1}{2^{n+2}}\right) - n\left(\frac{1}{2^{n+1}}\right) - \left(\frac{1}{2^{n+1}}\right) + \left(\frac{1}{2}\right)}{\left(-\frac{1}{2}\right)^2} $

$ \Rightarrow \sum\limits_{i=0}^n i\left(\frac{1}{2}\right)^{i} = \frac{\frac{n}{2^{n+2}} - \frac{n + 1}{2^{n+1}} + \frac{1}{2}}{\left(\frac{1}{4}\right)} $

$ \Rightarrow \sum\limits_{i=0}^n i\left(\frac{1}{2}\right)^{i} = 4 \left( \frac{n}{2^{n+2}} - \frac{n + 1}{2^{n+1}} + \frac{1}{2} \right) $

$ \Rightarrow \sum\limits_{i=0}^n i\left(\frac{1}{2}\right)^{i} = 4 \left( \frac{n}{2^{n+2}} - \frac{2(n + 1)}{2^{n+2}} + \frac{2^{n+1}}{2^{n+2}} \right) $

$ \Rightarrow \sum\limits_{i=0}^n i\left(\frac{1}{2}\right)^{i} = \frac{n - 2(n + 1) + 2^{(n+1)}}{2^{n}} $

$ \Rightarrow \sum\limits_{i=0}^n \frac{i}{2^{i}} = \frac{n - 2(n + 1) + 2^{(n+1)}}{2^{n}} $