Community,
currently I am trying to solve the following recurrence by substitution:
$$ T(n)= \begin{cases} c & \text{if n=1} \\ 2T(\frac{n}{2})+c*n\,\log\,n & \text{if n>1} \end{cases} $$
My progress:
Guessing the solution: $$ n\ \log\ n $$
To show: $$ T(n) \leq c*n\ \log\ n $$
Proof by Induction:
$$ T(1)= c\leq c*1\ \log\ 1= c \leq c*0 $$ $$ T(2)= 2(\frac{2}{2})+c*2\ \log\ 2 = 2+c*2 \leq c*2 $$
The problem is that there is not existing an c>0 which makes this inequality true, because the left equation will always be larger.
I think I did a mistake. Can somebody show me where I did a mistake?
sincerely, M.Hisoka
If $T(n) =2T(n/2)+c*n\log n $, put $n = 2^m$ to get $T(2^m) =2T(2^{m-1})+c*m2^m $, with maybe a different $c$ depending on the base of logs.
Dividing by $2^m$, this becomes $\dfrac{T(2^m)}{2^m} =\dfrac{T(2^{m-1})}{2^{m-1}}+c*m $.
Letting $U(m) =\dfrac{T(2^m)}{2^m} $, this becomes $U(m) =U(m-1)+cm $ for which the solution is $U(m) =cm(m-1)/2+U(0) $.
Working backwards, $\dfrac{T(2^m)}{2^m} =cm(m-1)/2+U(0) $, so $T(2^m) =2^m(cm(m-1)/2+U(0)) $.
Replacing $m$ by $\lg n$, this becomes $T(n) =n(c\lg^2(n)+O(1)) $.
Therefore the exact order of $T(n)$ is $\Theta(n \ln^2(n))$.
Whenever you have $T(n) =aT(n/b)+f(n)$, replacing $n$ by $b^m$ will get this type of solution.
If the recurrence is $T(n) =aT(n^{1/b})+f(n) $ (the usual case is $b = 2$), the substitution that converts it to a linear recurrence is $n = b^{b^m}$.