1
$\begingroup$

I have a recurrence relation as follows

$$T(n) = 2T(\lfloor n/2\rfloor) + n\log(n)$$

Using the induction hypothesis how do I obtain a relation $T(n)\leq E$ such that $E$ contains neither $T$ nor floor operator ($\lfloor\cdot\rfloor$).

$\endgroup$
3
  • $\begingroup$ Well, what is your induction hypothesis? Or are you just asking for an induction-based proof for some bound? If that is the case, do you want an optimal bound? If not, you should be able to prove that $T(n) \leq 2^n$, for example. $\endgroup$ Sep 8, 2020 at 21:07
  • $\begingroup$ I don't see any induction hypothesis here... $\endgroup$ Sep 9, 2020 at 8:50
  • $\begingroup$ Would be clearer to write $E(n)$. $\endgroup$
    – user16034
    Jun 2, 2022 at 10:58

1 Answer 1

0
$\begingroup$

We can open up the recursion to obtain \begin{align} T(n) &\leq n \log n + 2\lfloor n/2\rfloor \log \lfloor n/2 \rfloor + 4\lfloor \lfloor n/2 \rfloor/2\rfloor \log \lfloor \lfloor n/2 \rfloor/2\rfloor \\ &\leq n\log n + n \log (n/2) + n\log (n/4) + \cdots \\ &\leq n\log n + n\log n + \cdots \\ &= O(n\log^2 n), \end{align} since it takes $\Theta(\log n)$ steps to get to the base case.

If you're more careful, you can show that in fact $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.