# 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)

-

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.

-

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

-
I think I was not clear when I used the term "solution", so I will clarify: 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. – zvisofer Nov 12 '12 at 18:38
It doesn't hold with O(n) since for instance x=n/2 for all stages yields O(nlogn). – zvisofer Nov 12 '12 at 18:45
Just to translate it into mathematics, do you mean that $x$ is really a function of $n$, and your recurrence holds for $x(n)$, and you want an estimate that is uniform over all such $x$? – Alexander Shamov Nov 12 '12 at 18:50
I added clarification. please tell me if now the question is clear or you have more questions. – zvisofer Nov 12 '12 at 18:54
I can't stress enough that x is not a function of n. let say that x is chosen randomely every time one step of the recursion is made, and I am interested in minimum upper bound that fits for all possible scenarios. – zvisofer Nov 12 '12 at 19:01