# Solving $T(n)= 2T(n/2)+n \lg (n)$

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?

-
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

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

-

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}

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

-
Thanks. Which case of master theorem? Can you provide more information? –  practic_pom Nov 7 '11 at 21:06
@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