Asymptotic runtime of recursive algorithm uisng subsitution method I need to solve this question using the substitution method:
$T(n) = 3T(n/2)+2n$ if  $n&gt;1$ otherwise,  $T(n) = 1$
Note: $$\sum_{i=0}^k x^i = \frac{x^{k+1}-1}{x-1}$$
$$a^{\log_b n} = n^{\log_b a}$$

I made some attempts at it but I haven't been able to recognize the pattern. It looks to me that it will be  $\mathcal{O}(n \log n)$ but I'm having a hard time proving it.

The substitution method: Substitute the right-hand side of the equation into any recursive instances that appear on the right-hand side:
$$T(n) = c + T(n-1)$$
$$T(n) = c + [c + T((n-1)-1)] = c + [c + T(n-2)]$$
$$T(n) = c + [c + [c + T(n-3)]]$$
$$...$$
$$T(n) = c+c+...+c + T(0)$$
$$T(n) = nc + T(0)$$
So $T(n) \in  \mathcal{O}(n)$
Here is an argument by substitution:
$$\begin{aligned}
T(n) &amp;= 3T(n/2)+2n \\&amp;= 3(3T(n/4)+n)+2n \\&amp;= 3(3(3(T(n/8)+n/2)+n)+2n \\&amp;= \cdots \\&amp;= 3^kT(n/2^k)+\sum_{i=0}^{k-1}{2n\left(\frac{3}{2}\right)^i} \\&amp;= 3^kT(n/2^k)+2n\frac{\left(\frac{3}{2}\right)^k-1}{\left(\frac{3}{2}\right)-1} \\&amp;= 3^kT(n/2^k)+4n\left(\frac{3}{2}\right)^k-4n
\end{aligned}$$
Here, we stop to expand terms when $n/2^k=1$, or equivalently, when $k=log_2n$. Using that knowledge and the identity that you wrote in your question, we get that:
$$\begin{aligned}
T(n) &amp;= 3^{log_2n}T(1)+4n\left(\frac{3}{2}\right)^{log_2n}-4n \\&amp;= n^{log_2{3}}+4n\cdot n^{log_2\frac{3}{2}}-4n \\&amp;= \cdots \\&amp;= 5n^{log_2{3}}-4n \\&amp;\in\mathcal{O}(n^{log_2{3}})
\end{aligned}$$
So as you can see, the fact that you have a factor 3 outside and a factor 2 inside makes your runtime polynomial in $n$.