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)