# How to solve $T(n)\leq n^2+n\left[T(n-m)+T(m-1)\right]$?

I am trying to find $T(n)=O(f(n))$, where $$T(n)\leq n^2+n\left[T(n-m)+T(m-1)\right],$$ where $m\in\{1,2,\ldots,n\}$.

Is it possible to find $f(n)$ such that $T(n)=O(f(n))$?

I started to fix $m=n/2$ (which I assume the worst scenario, isn't it?). I found \begin{align}T(n)&\leq n^2+\frac{n^3}{2}+\frac{n^4}{8}+\frac{n^5}{64}+\frac{n^4}{4}T(n/16),\\ &\;\vdots\\& \leq n^2+T(1)\sum_{i=1}^{(\lg n)-2}\frac{n^{i+2}}{\sqrt{2^{i(i+1)}}}.\end{align}

• Why do you think $m = n/2$ is the worst case? It's not so clear. For example, it might be that $m=1$ is worse. Indeed, by choosing $m = n-1$, we get a lower bound of roughly $n^n$, compared to your $n^{\log n}$. Aug 19, 2018 at 22:24
• @YuvalFilmus Thanks for the comment. At first, I thought that having $T(n/2)+T(n/2)$ (two terms) would be worse than having $T(n-1)$ (one term), but as you mentioned, it isn't the worst case.
– zdm
Aug 19, 2018 at 22:34

On the one hand, we have \begin{align*} T(n) &\geq n^2 + nT(n-1) \\ &\geq n^2 + n(n-1)^2 + n(n-1) T(n-2) \\ &\geq n^2 + n(n-1)^2 + n(n-1)(n-2)^2 + n(n-1)(n-2)T(n-3) \end{align*} and so on. Assuming, for simplicity, a base case of $T(0) = 0$, this gives \begin{align*} T(n) &\geq n^2 + n(n-1)^2 + n(n-1)(n-2)^2 + \cdots + n(n-1)\cdots (1)^2 \\ &= n! \left(\frac{n}{(n-1)!} + \frac{n-1}{(n-2)!} + \cdots + \frac{1}{0!} \right) \\ &= n! \left(n + \frac{1}{(n-1)!} + \frac{1}{(n-2)!} + \cdots + \frac{1}{1!}\right) \\ &= n! \left(n + e - 1 \right) - O(1). \end{align*} This should also work as an upper bound. To prove this rigorously, choose an upper bound $S(n)$ for which you can prove $S(n) \leq n^2 + n(S(n-1) + S(0))$ as well as that $S(n)$ is convex. Convexity will ensure that the values of $m$ maximizing the sum $S(n-m) + S(m-1)$ are $m=1$ and $m=n$.