Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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}$$
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$.
