Solving recuurence equation $T(n)=3T(n/2)+cn$

Question

Please check my solving process.

Using recursion tree method for $T(n)=3T(n/2)+cn$,

\begin{align} T(n)&=\sum_{i=0}^{\log_2 n}\frac{3^i}{2^i}cn\\ &=cn\sum_{i=0}^{\log_2 n}(\frac{3^i}{2^i})\\ &=cn\frac{(\frac{3}{2})^{{\log_2 n}+1}-1}{\frac{3}{2}-1}\\ &=cn\frac{(\frac{3}{2})^{{\log_2 n}+1}-1}{\frac{1}{2}}\\ &=2cn(\frac{3}{2})^{{\log_2 n}+1}-2cn\\ &=2cn(\frac{3^{\log_2 n}}{n})-2cn\\ &=6c3^{{\log_2 n}+1}-2cn\\ &\approx6c3^{{\log_2 n}+1}\\ &=\theta(n^{\log_2 3}) \end{align}

Am I right?

Answer 1

actually we get the following solution $$T(n)=c_1 3^{\frac{\log (n)}{\log (2)}-1}-2 c \left(n-3^{\frac{\log (n)}{\log (2)}}\right)$$