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?
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}) $