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 a recursive function: $$ T(n)= 2 T(n/2)+n \lg(n), \quad n>2,\quad T(2)=2,\quad n = 2^{k}$$

Master theorem didn't work. The result is pointless (if I did it right).

Any suggestions?

share|improve this question
    
You mean the "master theorem"? –  Srivatsan Nov 7 '11 at 20:53
    
Doesn't seem to be well defined if $n$ is not a power of 2. Or is there some rounding going on? Is there a base case like $T(1)=0$? –  Henning Makholm Nov 7 '11 at 21:02
    
Edited my question. –  practic_pom Nov 7 '11 at 21:04
    
Still not defined when $n$ is not a power of $2$, unless you mean $2T(\lfloor n/2 \rfloor)...$ –  Thomas Andrews Nov 7 '11 at 21:18
    
The Master theorem does apply here... we have $a = 2$ and $b = 2$ and since $f(n) = n\lg{n} = \Theta(n^{\log_2{2}}\lg{n})$, it immediately follows that $T(n) = n\lg^2{n}$ by the second case of the Master theorem. –  Zach Langley Nov 7 '11 at 22:49

3 Answers 3

up vote 7 down vote accepted

I prefer to resort to ad-hoc tricks for solving such recursions. Divide by $n$ to get: $$ \frac{T(n)}{n} = \frac{T(n/2)}{(n/2)} + \lg n. $$ Assuming $n$ is a power of $2$, it is easy to see that $$ \begin{eqnarray*} \frac{T(n)}{n} &=& \lg (n) + \lg \left( \frac{n}{2} \right) + \lg \left( \frac{n}{2^2} \right) + \cdots + \lg (1) \\ &=& \lg n + (\lg n - 1) + (\lg n -2) + \cdots + 0 \\ &=& \frac{1}{2} \lg n \cdot (\lg n +1) \\ &=& \Theta((\lg n)^2), \end{eqnarray*} $$ which implies $T(n) = \Theta(n (\lg n)^2)$.

It is conventional to hand-wave at this point and mumble something about $n$ not a power of $2$...

share|improve this answer

The recurrence only seems to be well defined when $n$ is a power of $2$, so let $n=2^k$. Then we can expand the recurrence until we reach T(2): $$\begin{align}T(2^k) &= 2^kk + 2\cdot 2^{k-1}(k-1) + 2^2\cdot2^{k-2}(k-2) + \cdots + 2^{k-2}\cdot 2^2 2 + 2^{k-1}2 \\ &= 2^k \sum _{j=1}^{k} j = 2^k\frac{k(k+1)}{2} = 2^{k-1}k(k+1)\quad \mathrel{\Big[=} O(n\log^2(n))\Big]\end{align}$$

share|improve this answer
    
I have added $T(2)=2$. My mistake. –  practic_pom Nov 7 '11 at 21:09
    
Answer edited with new information –  Henning Makholm Nov 7 '11 at 21:15

While one case of the master theorem easily applies, this one is also simple enough that it can be solved via induction. Consider $$\begin{align*}T(2^k) &= k2^k + 2T(2^{k-1})\\ &= k2^k+2\bigl((k-1)2^{k-1}+2T(2^{k-2})\bigr) \\ &= k2^k+(k-1)2^k+4T(2^{k-2}) \end{align*}$$ etc; you should be able to continue this to find the value of $T(2^k)$, and then use that to prove that the asymptotic result holds for values of $n$ that aren't powers of $2$.

share|improve this answer
    
Thanks. Which case of master theorem? Can you provide more information? –  practic_pom Nov 7 '11 at 21:06
1  
@practic_pom: Looks to me like Case 2 Generic Form on en.wikipedia.org/wiki/Master_theorem –  Ross Millikan Nov 7 '11 at 21:10

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.