[Solved]: Asymptotic equivalent of the recurrence T(n)=3⋅T(n/2)+n

Problem Detail: 

The questions is to find the running time $T(n)$ of the following function:

$$T(n)=3\cdot T(n/2) + n \tag{1}$$

I know how to solve it using Master theorem for Divide and Conquer but I am trying to solve it by expanding: $$\textstyle T(n) = n+\frac{3}{2}n +(\frac{3}{2})^2n + (\frac{3}{2})^3n + \cdots \tag{2}$$ which implies $$T(n)=n\sum_{k=1}^{n}({\textstyle \frac{3}{2}})^{k-1} \tag{3}$$ and so $$T(n)=2n\cdot(({\textstyle\frac{3}{2}})^n-1) \tag{4}$$

The right answer to this problem is $\Theta(n^{\log3})$. How can I reach to right answer through my approach as shown above.Is my approach wrong ? How can I solve it without using Master theorem.

Any help is appreciated.

Asked By : Aditya pratap singh

Answered By : Rick Decker

Your approach is almost correct, except for the fact that the upper limit of your summation should be $\log_2n$, rather than $n$. You should have $$ T(n)=3^kT\left(\frac{n}{2^k}\right)+\left[n\left(\frac{3}{2}\right)^{k-1}+n\left(\frac{3}{2}\right)^{k-2}+\dotsm+n\left(\frac{3}{2}\right)^0\right] $$ and your goal is to drive $n/2^k$ down to a value that will allow you to replace $T(n/2^k)$ with to a value you know, like, say, $T(1)$. That will happen when $n=2^k$ so $k=\log_2n$. Using that value for $n$ gives you $$\begin{align} T(n)&=3^{\log_2n}T(1)+n\sum_{j=1}^{\log_2n}\left(\frac{3}{2}\right)^{j-1}\\ &=3^{\log_2n}T(1)+2n\left[\left(\frac{3}{2}\right)^{\log_2n}-1\right]\\ &=n^{log_23}T(1)+2n[n^{\log_2(3/2)}-1]\\ &= n^{\log_23}T(1)+n^{log_23}-2n\\ &= \Theta(n^{\log_23}) \end{align}$$

Best Answer from StackOverflow

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

 Ask a Question

 Download Related Notes/Documents