Recurrence relation $T(n) = T(n/2) + n\log(n)$

Question

So I've been working on this recurrence equation and I'm stumped at the end. $T(n) = T(n/2) + n\log(n);\: T(1) = 1;\: n = 2^k$ and $\log $ is base $2$.

$T(2^k) = T(2^{k-1}) + 2^k \log(2^k)$

$T(2^k) = T(2^{k-1}) + (2^k) k$

$T(2^{k-1}) = T(2^{k-2}) + 2^{k-1} \log (2^{k-1})$

$T(2) = T(1) + 2^{1}\cdot(1)$

$T(1) = 1$

$T(2^k) = 1 + \displaystyle \sum_{i=0}^{ k} (2^i) (k-i)$

I'm not sure if I did everything correct, but I'm confused about tackling the summation.

Answer 1

Your working is mostly fine, except the final summation.

So for any $i\geq1$, as you showed: \begin{align*} T(2^i)&=T(2^{i-1})+i\cdot2^i \\ \implies T(2^i)-T(2^{i-1})&=i\cdot2^i \\ \implies \sum_{i=1}^k (T(2^i)-T(2^{i-1})) &= \sum_{i=1}^k i\cdot2^i \end{align*}

The left side telescopes, giving $T(2^k)-T(1)=T(2^k)-1$, so we have

$$T(2^k)=1+\sum_{i=1}^k i\cdot2^i$$

Now, to evaluate this summation, I'm not too sure of a direct way of the top of my head. If you happen to know it in advance, its not too bad to prove by induction.

I claim that $$\sum_{i=1}^k i\cdot2^i=(k-1)2^{k+1}+2$$

You can check it holds when $k=1$. Suppose it holds when $k=n$. Then:

\begin{align*} \sum_{i=1}^{n+1}i\cdot2^i&=(n+1)2^{n+1}+\sum_{i=1}^n i\cdot2^i \\ &=(n+1)2^{n+1}+(n-1)2^{n+1}+2 \\ &= n2^{n+2}+2 \\ &= ((n+1)-1)2^{(n+1)+1}+2 \end{align*}

So the formula also holds when $k=n+1$. This proves the clame, and consequently

$$T(2^k)=1+(k-1)2^{k+1}+2=(k-1)2^{k+1}+3$$

If you wanted to rewrite this in terms of $n$, just use the fact that $2^k=n$ and $\log n=k$ (using $\log$ to base 2). Then, provided $n$ is a power of 2, the recurrence becomes:

$$T(n)=2n(\log(n)-1)+3$$

Answer 2

To assure you about the summation I separated the terms of the final sums in a likely better patternizable form:
$ \qquad \qquad \displaystyle \small \begin{array} {} T(1)&=&1 &=&1&=&3-1\cdot2\\ T(2^1)&=&1+1 \cdot2^1 &=&3&=&3+0\cdot4 \\ T(2^2)&=&1+1 \cdot2^1+2 \cdot2^2 &=&11&=&3+1\cdot8\\ T(2^3)&=&1+1 \cdot2^1+2 \cdot2^2 +3 \cdot2^3 &=& 35&=&3+2\cdot16\\ T(2^4)&=&1+ ...+4 \cdot2^4 &=& 99&=&3+3\cdot32\\ T(2^5)&=&1+ ...+5 \cdot2^5 &=& 259&=&3+4\cdot64\\ \end{array}$

The pattern $1x+2x^2+3x^3+4x^4+...$ (where here $x=2$) can also be represented by a generating function of the style $ a/ (1-x)^2$ and this can be adapted to match the sum-expressions above as truncation of the occuring series to make the final formula below rigorous. This is the generating function:

$ \qquad \qquad \displaystyle G(m,x)= 1+{x \cdot (1-x^{m+1})-(m+1) \cdot x^{m+1} \cdot (1-x) \over (1-x)^2}$
From this, evaluated at $x=2$ we get the expression for $T(n$)

$ \displaystyle \qquad \qquad T(n)=G(\log_2(n),2) \\ \qquad \qquad \qquad = 1+2 \cdot { (1-2^m)+m \cdot 2^m \over (-1)^2} \qquad \qquad \qquad \text{ ( where } m=\log_2(n) \text{ )}\\ \qquad \qquad \qquad = 1+2 \cdot (1-n+\log_2(n) \cdot n) $

and finally

$ \qquad \qquad \displaystyle { T(n) = 3 + (\log_2(n)-1)\cdot2 \cdot n }$

(which is the result as was previously given in the answer of pjhuxford)