2
$\begingroup$

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.

  • 0
    No. sorry, I fi$x$ed it.2011-07-08

3 Answers 3

4

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

0

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

  • 0
    The $\Theta$ notation means that $T(n) \le \alpha n$ for some \alpha > 0 and $T(n) \ge \beta n$ for some \beta > 0.2011-07-08
0

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

  • 0
    I think functions $T(n)$ that appear in analysis of algorithms as the running times are usually assumed to be increasing (non-decreasing). In any case, they are defined on the integers. (So the question should *actually* ask about $T(n) = T(\lfloor cn \rfloor) + T(\lfloor dn \rfloor) + n$ or $T(n) = T(\lceil cn \rceil) + T(\lceil dn \rceil) + n$.) So it doesn't make much sense in this context to consider functions that depend on whether the argument is rational or irrational.2011-07-09