I am trying to solve the recurrence relation:
$ t(n)= 3T(n/2)+Cn$ (if $n>2$)
$t(2)=C$ (otherwise)
I know that there is the Master Theorem but I am trying to use the tree method. This is what I have so far: the total work that was done in each level is: $Cn(q/2)^j$ there are $\log n$ levels and therefore the sum of the work can be represented with the following geometric series:
$Cn\sum_{j=0}^L(3/2)^j$
$L=\log_2 n-1$
It's obvious that the ratio is greater than 1. Is there a way to solve this? I can't find an answer anywhere