Analysis of Algorithms: Solving Recursion equations: $\quad T(n)= T(cn)+T(dn)+n$

Question

How can I prove that the solution for the following recursion equation is $\Theta(n)$:

$$T(n)= T(cn)+T(dn)+n \text{ for } d,c>0 \text{ and } c+d<1$$

---

Edit: $cn$ on one side only. What I need to show is that algorithm that works this way it will "waste" linear time of work, depending on $n$ , the amount of values that it will need to work on, I hope I got that clear.

Answer 1

This idea might help a litte:

First lets try to homogenize it: look for some $g(n)= T(n)-xn$ which kills the free term.

This becomes:

$$g(n)+xn=g(cn)+cxn+g(dn)+dxn+n \,.$$

Thus we need

$$x=cx+dx+1 \Rightarrow x= \frac{1}{1-c-d} \,.$$

Thus the function

$$g(n)= T(n) -\frac{n}{1-c-d} \,,$$

verifies the recurence

$$g(n)= g(cn)+g(dn) \,.$$

It should be an easy induction problem to prove now that $g(n) \leq \alpha n$ for some $\alpha> 0$, is that what you need? The $\Theta$ notation is a little confusing....

P.S. Also note that if the first "few" $g(n)$ are non-negative, it is easy to show that $g(n) \geq 0$... Few here depends on what $c,d$ actually are...

Answer 2

This linear functional equation has a particular solution $T(n) = \frac{n}{1-c-d}$.
To this you can add a solution of the homogeneous equation $f(n) = f(cn) + f(dn)$. Now actually this has solutions that are not $O(n)$. For example, suppose $c = d$ and no nonzero integer power of $c$ is rational, and let $f(n) = (2 c^2)^{m} n^2$ if $n c^m$ is rational for some integer $m$, 0 if $n c^m$ is irrational for all integers $m$.

Answer 3

Since $T(n) > n$, we immediately have $T(N) = \Omega(n)$.

To get the desired upper bound, we can apply the Master Theorem (technically, a generalization known as the Akra-Bazzi method). However, since we already know that the answer is $O(n)$ and just need to prove it, a simple induction argument suffices.

Let $c+d=1-\epsilon$. Suppose that $T(m) < \alpha m$ for all $m < n$. Then $T(n) < \alpha cn + \alpha dn + n = (c + d)\alpha n + n = (1-\epsilon)\alpha n + n$.

We want that $T(n) < \alpha n$. Solving $(1-\epsilon)\alpha n + n < \alpha n$, we see that the inequality holds provided that $\epsilon\alpha > 1$.

So $T(n) < \alpha n$ for all $n$, where $\alpha = (1-c-d)^{-1}$.