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$


$$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$


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


$$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$).

Then (please check the details),

$$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$$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.