2
$\begingroup$

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

$\endgroup$
  • 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$ – Yuval Filmus Aug 19 '18 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 '18 at 22:34
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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