Problem Detail: The questions is to find the running time $T(n)$ of the following function: $$T(n)=3cdot 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)=nsum_{k=1}^{n}({textstyle frac{3}{2}})^{k-1} tag{3}$$ and so $$T(n)=2ncdot(({textstylefrac{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^kTleft(frac{n}{2^k}right)+left[nleft(frac{3}{2}right)^{k-1}+nleft(frac{3}{2}right)^{k-2}+dotsm+nleft(frac{3}{2}right)^0right] $$ 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)+nsum_{j=1}^{log_2n}left(frac{3}{2}right)^{j-1} &=3^{log_2n}T(1)+2nleft[left(frac{3}{2}right)^{log_2n}-1right] &=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
