Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
6  
What if $n$ is odd? And what is $T(1)$? –  TonyK Jan 25 '12 at 11:30

3 Answers 3

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

share|improve this answer

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}} $$

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.