Help Solve Recurrence Relation T(n) = 3T(n/2) + O(n) Given recurrence $$T(n) = 3T(n/2) + O(n)$$
$$let\:cn >= O(n)$$ for some constant c I can bound $$T(n)$$ in terms of $$T(n/2)$$
so I have $$T(n) <= 3T(n/2)+cn, \ \ \ \ \  k = 1 \ call$$ 
So I expanded the recurrence a few times and got
$$T(n) <= 9T(n/4)+2cn, \ \ \ \ \  k = 2  \ calls$$
$$T(n) <= 27T(n/8)+3cn, \ \ \ \ \  k = 3  \ calls$$
The emerged pattern is 
$$T(n) <= 3^kT(n/2^k)+kcn, \ \ \ \ \  k^{th} \ call$$

Solving for k: $n/2^k = 1$ 
$ \  \ \ \ \ \ \ \ \ \ \ \ \ \ $ I have  k = $\log_2 n$  
Im not sure where to go from here? 
 A: Is this from CLRS book?
In my opinion, the best way to solve this is by using the recursion tree method. You can see that the pattern is:
$ \frac{n}{2^i} = 1 \\
i = lg(n) \\
 $
Then the tree has $ lg(n) $ levels.
The tree has $ 3^i $ nodes at the last level, which give us the cost:
$ 3^i = 3^{lg(n)} = n^{lg(3)} $
Now we have to calculate the cost for each node! Since we know that each level has a linear cost form ($ \theta(n) $), we can multiply this cost by the number of nodes at each $i^{th}$ level:
$ 3^ic(\frac{n}{2^i}) = nc(\frac{3}{2})^i $
Great! The only thing left is to sum this cost for all levels, including the last level, for which we know that the cost is $n^{lg(3)}$:
$ T(n) = \sum_{i=0}^{lgn - 1} nc(\frac{3}{2})^i + \theta(n^{lg3}) $
$ \quad\quad = nc \sum_{i=0}^{lg n - 1} (\frac{3}{2})^i + \theta(n^{lg3}) $ 
Clearly, this is a geometric series. Then, we can use the propriety:
$ \sum_{k=0}^{n} x^k = \frac{x^{n+1} - 1}{x - 1} $
Applying the propriety we have: 
$ T(n) = nc(\frac{(3/2)^{lgn} - 1}{(3/2) - 1}) + \theta(n^{lg3}) \\ 
  T(n) = nc(3^{lgn} - 2) + \theta(n^{lg3}) \\
  T(n) = \theta(n^{lg3}) $
