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$).

  • $\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$ – Watercrystal Sep 8 '20 at 21:07
  • $\begingroup$ I don't see any induction hypothesis here... $\endgroup$ – Yuval Filmus Sep 9 '20 at 8:50

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)$.


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.