[Solved]: Running time of recursive algorithm with geometric series

Problem Detail: 

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.

Asked By : dos

Answered By : hengxin

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41041

3.2K people like this

 Download Related Notes/Documents