# Using inductive hypothesis on recurrence relation?

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

• 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. – Watercrystal Sep 8 '20 at 21:07
• I don't see any induction hypothesis here... – 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)$$.