# Running time of recursive algorithm with geometric series

What is the complexity of the recurrence $T(n) = 3T(\frac n2) + O(n)$?

So far I have:

$O(n) \le cn$ for some constant $c$

Hence:

$$T(n) \le 3T(\frac{n}{2}) + cn$$

After a recursion:

$$T(n) \le 3(3T(\frac{n}{4}) + \frac{cn}{2}) + cn$$ $$= 9T(\frac{n}{4}) + \frac{3cn}{2} + cn$$

After another recursion:

$$T(n) \le 9(3T(\frac{n}{8}) + \frac{cn}{4}) + \frac{3cn}{2}+ cn$$ $$= 27T(\frac{n}{4}) + \frac{9cn}{4} + \frac{3cn}{2} +cn$$

The general term is:

$$T(n) \le 3^{k}T(\frac{n}{2^k}) + \frac{\sum_{i = 0}^k{3^i}}{\sum_{i = 0}^k{2^i}}cn$$

For some $k$

Now:

$$\sum_{i = 0}^k{(\frac{1}{2})^i} = \frac{1}{1-\frac{1}{2}}$$ $$= 2$$

Hence:

$$T(n) \le 3^{k}T(\frac{n}{2^k}) + 2\sum_{i = 0}^k{3^i}cn$$

I do not know how to proceed from here.

This question is from Algorithms; Dasgupta, Papadimitriou, Vazirani; 1st Edition. Question 2.3 (a)

Thank you.

$$T(n) \le 3^{k}T(\frac{n}{2^k}) + \sum_{i = 0}^k{(3/2)^i} cn$$
The recursion will reach the base case when $2^k = n$ (i.e., $k = \log n$). And it is common to suppose the base case is $T(1) = 1$ (or $T(1) = d \textrm{ for some constant } d$).
$$T(n) \le 3^{\log n} + \sum_{i = 0}^{\log n}{(3/2)^i} cn = n^{\log 3} + 3cn^{\log 3} - 2cn = (3c+1) n ^{\log 3} - 2cn$$