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
    Is $T(cn)$ on both sides?2011-07-08
  • 0
    No. sorry, I fixed it.2011-07-08

3 Answers 3