Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
add comment

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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