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.
