1
$\begingroup$

Solving $T(n) = 2T(\frac{n}{2}) + n\log(n)$ without master theorem, given $T(1) = 1$

My approach with recurrence tree:

$n \sim n\log(n)$

$\frac{n}{2} \sim 2 \frac{n}{2}\log(\frac{n}{2})$

$\frac{n}{4} \sim 4 \frac{n}{4}\log(\frac{n}{4})$

Hence the summation must follow as:

$$T(n) = \sum_{i=0}^{\log(n)} n\log(\frac{n}{2^i})$$ $$= \sum_{i=0}^{\log(n)} n(\log(n) - i)$$ $$=(n\log(n) \sum_{i=0}^{\log(n)}i) - (\sum_{i=0}^{\log(n)} i)$$

I can not go further from here, any help is welcome.

$\endgroup$
1
$\begingroup$

For direct result let's use direct summation assuming $n=2^k$: $$T(n) = 2T\left(\frac{n}{2}\right) + n\log(n)=2\left[ 2T\left(\frac{n}{2^2}\right) +\frac{n}{2}\log \frac{n}{2}\right]+ n\log(n) = \\ =2^2T\left(\frac{n}{2^2}\right)+n\log \frac{n}{2}+ n\log(n) =\\ =\cdots=\\ =2^kT\left(1\right)+n\log \frac{n}{2^{k-1}}+ \cdots +n\log \frac{n}{2}+n\log(n)=\\ =2^kT\left(1\right) +n\log 2 + \cdots +n\log 2^k=\\ =nT\left(1\right) +n\log 2 (1 + \cdots + k) =nT\left(1\right) + \frac{k(k+1)}{2} n\log 2 \in \Theta (n \log^2 n)$$ where, of course, $k=\log_2 n$. Hope you can obtain from here everything what you wanted.

At end let me note also, that $n \sim n\log(n)$ and other equivalences, which you are using, are not correct, if we understand standard $\lim \frac{f}{g}=1$, for symbol "$\sim$". Correct is, for example, $n = o(n\log(n))$ etc.

$\endgroup$
1
  • $\begingroup$ Also thanks for your hint. $\endgroup$ – Sophie Roseinsta Mar 16 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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