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.