# Asymptotic equivalent of the recurrence T(n)=3⋅T(n/2)+n

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.

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}
You have a mistake going from (2) to (3) because you lost $n$ and it is not clear why your sum should range from $i = 1$ to $i = n$ (it does not). Then it is not clear how you got from (3) to (4) where $n$ reappeared. Perhaps you just los $n$ in (3) but otherwise you had it on paper.
Let us try again: \begin{align*} T(n) &= n + (3/2) n + (3/2)^2 n + \cdots \end{align*} But when does sum end? (This is what created your mistake.) It ends when we get to the base case, which is $T(1)$. After $k$ unfoldings we have $T(n/2^k)$ so we will reach $T(1)$ when $k = \log_2 n$. Thus, we continue like this: \begin{align*} T(n) &= n + (3/2) n + (3/2)^2 n + \cdots + (3/2)^{\log_2 n} T(1) \\ &= \textstyle \sum_{i=0}^{\log_2 n} (3/2)^i n\\ &= n \cdot \textstyle \sum_{i=0}^{\log_2 n} (3/2)^i. \end{align*} It remains to add the sum. It is a geometric series, so we can look up the formula $\sum_{i=0}^k a^i = (a^{k+1} - 1)/(a - 1)$ and get \begin{align*} {\textstyle \sum_{i=0}^{\log_2 n} (3/2)^i} &= \frac{(3/2)^{1 +\log_2 n} - 1}{3/2 - 1} \\ &= 2 \cdot ((3/2) \cdot (3/2)^{\log_2 n} - 1) \\ &= 3 \cdot (3/2)^{\log_2 n} - 2 \\ &= 3 \cdot (n^{\log_2 (3/2)}) - 2 \\ &\in \Theta(n^{\log_2 (3/2)}) \approx \Theta(n^{0.58}) \end{align*} The final result is this sum multiplied with $n$, so it is $$\Theta(n \cdot n^{\log_2(3/2)}) = \Theta(n^{\log_2 2 + \log_2 (3/2)}) = \Theta(n^{\log_2 3}),$$ assuming I can still do logarithms....
You are correct that \begin{align*} T(n) &= n + \tfrac{3}{2} n + (\tfrac{3}{2})^2 n + \cdots + (\tfrac{3}{2})^{k-1} n + 3^k T(n/2^k) \\ &= n \sum_{t=0}^{k-1} (\tfrac{3}{2})^t + 3^k T(n/2^k) \\ &= 2[(\tfrac{3}{2})^k-1]n + 3^k T(n/2^k). \end{align*} Let's assume that $n$ is a power of $2$, and the base case is $T(1) = C$. In order to reach the base case, we need to choose $k$ so that $n = 2^k$. In other words, we need to take $k = \log_2 n$. We then have $3^k = n^{\log_2 3}$ and $(3/2)^k = n^{\log_2 3 - 1}$. Substituting these values, we find out that $$T(n) = 2[n^{\log_2 3-1}-1]n + Cn^{\log_2 3} = (C+2)n^{\log_2 3} - 2n.$$ This shows the stronger result $$T(n) \sim (C+2) n^{\log_2 3},$$ which implies $T(n) = \Theta(n^{\log_2 3})$.