What's the simplest way to prove that the solution for this recursion equation: $T(n)=T(\frac{n}{4})+T(\frac{3}{4}n)+1$ ,
is $T(n)=\theta (n)$?
I think that it is $T(n)=\theta (n)$ because it is just +1 in every iteration and it looks like it will do that n times, but I'm not sure.
Thank you