Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

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|cite|improve this question

marked as duplicate by Famous Blue Raincoat, dustin, Joel Reyes Noche, anomaly, Claude Leibovici Feb 26 '15 at 5:36

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new 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
up vote 8 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|cite|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|cite|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|cite|improve this answer
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 – Ross Millikan Nov 7 '11 at 21:10

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