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}$$

  • 2
    $\begingroup$ 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}$. $\endgroup$ Aug 19, 2018 at 22:24
  • $\begingroup$ @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. $\endgroup$
    – zdm
    Aug 19, 2018 at 22:34

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.