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$
$\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$– WatercrystalCommented Sep 8, 2020 at 21:07
-
1$\begingroup$ I don't see any induction hypothesis here... $\endgroup$– Yuval FilmusCommented Sep 9, 2020 at 8:50
-
$\begingroup$ Would be clearer to write $E(n)$. $\endgroup$– user16034Commented Jun 2, 2022 at 10:58
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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)$.
answered Sep 9, 2020 at 8:53