solving a non-standard recurrence relation in asymptotic terms (using Big O notation) 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)
 A: 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$:


*

*$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;

*$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)$

*$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.
A: 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)$.
