# 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. Sep 8, 2020 at 21:07
• I don't see any induction hypothesis here... Sep 9, 2020 at 8:50
• Would be clearer to write $E(n)$.
– user16034
Jun 2, 2022 at 10:58

## 1 Answer

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