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$

2 Answers 2

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$ Mar 16, 2021 at 8:57
1
$\begingroup$

From your recursion, beacuse of $T(n)$ have a term $n\log n$ we can conclude that : $$T(n)=\Omega(n\log n)$$ and from your summation :

$$T(n)=n\log(n) \sum_{i=0}^{\log(n)}i - \sum_{i=0}^{\log(n)} i<n\log(n) \sum_{i=0}^{\log(n)}i\simeq n\log^2 n$$ Finally $$n\log n\leq T(n)\leq n\log^2 n$$ Next step, we try to improve lower bound by induction: Suppose $T(n)\geq c\times n\log^2 n$ $$\rightarrow 2\times c\times\frac{n}{2}\times \log^2 \frac{n}{2}+ n\log n\geq c\times n\log^2 n$$ $$=c\times n\times \log n\times(\log n+\frac{1}{c})\geq c\times n\times \log n\times(\log n+\frac{1}{\log n})\hspace{20pt}\text{if $c\leq$ 1 }\square$$ For sufficiently large $n$ (i.e. $n\to \infty$), and base case above inequality is correct. So we conclude that as $n\to \infty$ $$T(n)=\theta (n\log^2 n)$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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