solving a non-standard recurrence relation in asymptotic terms (using Big O notation)

Question

Looking at the following recurrence relation: $$ T(n)= T(n-x)+T(x)+O(\min(x,n-x)) $$ $$ T(1)=1 $$ where $x$ can devide our problem in any proportion (may vary from call to call -- not a constant function of $n$) I wonder if it is possible to show a better solution than $O(n^2)$ in this general case?

clarification: I don't get to choose x. I should show that T(n)=O(f(n)) for every possible x, at every possible stage of the recursion (Think of this as if at every time n breaks into n-x & x, the actual value of x is chosen randomly from {1,2,...,n-1} and we want to show that our upper bound is right for every possible random selection).

(I ask this because I studied an algorithm that has complexity which is a private case of this recurrence relation, and I had to use some additional facts about the algorithm to prove complexity of $O(n\log n)$. But, I think that it may be a plain mathematical problem that can be solved in a more general case as I introduced here)

Answer 1

If I understood correctly, we should really solve something like

$\displaystyle T(n) \le \max_{1 \le x \le n-1} [T(x) + T(n-x) + C\min(x, n-x)], n \ge 2$,

which would correspond to the "worst-case solution" to the OP's problem.

It is convenient for me to assume that $T(1)=0$, which is possible by adjusting $C$ appropriately.

Let's prove by induction that $T(n) \le D \cdot n\ln n$ with some constant $D$ that only depends on $C$ in a way that will be specified later. Suppose that it is proven for $1,\dots,n-1$.

Then $\displaystyle T(n) \le \max_{1 \le x \le n/2} [D (x \ln x + (n-x) \ln (n-x)) + Cx]$.

The optimal $x \in [1,n/2]$ here is either $\alpha n$ for a fixed $\alpha = \frac{1}{1+\exp (C/D)} < 1/2$, or $n/2$, or $1$. In any case, it is easy to show that for $D$ sufficiently large and independent of $n$, $T(n) \le D n \ln n$:

1. $x = \alpha n$: $\displaystyle T(n) \le D n \ln n + (D \alpha \ln \alpha + D (1-\alpha) \ln (1-\alpha) + C \alpha) n \le D n \ln n$, since the second summand is negative for $D$ large;
2. $x = n/2$: $T(n) \le D n \ln n + (C/2 - D \ln 2) n \le D n \ln n$ if $D \ge C / (2 \ln 2)$
3. $x = 1$: $T(n) \le D (n-1) \ln (n-1) + C \le D n \ln n$ for all $n$, as long as $D$ is greater than $C / (2 \ln 2)$.

This proves the induction step.

Answer 2

This looks to me like an induction on $n$ shows that choosing $x=1$ all the time leads to $$T(n)=T(n-1) + T(1) + O(1) = (n-1 + O(1)) + 1 + O(1) = n+O(1)$$ so that should be $T(n)=O(n)$.