# 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>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)$$

• The solution can't be $O(n \log n)$. In fact, it must be $\Omega(n^c)$ for some $c>1$. – Steven Sep 24 at 21:25
• Since you are supposed to use a certain method it might be good to include your attempt at using the method and ask a question specific to that attempt. I believe that this will be more helpful to you compared to someone just giving a solution. – Watercrystal Sep 24 at 21:36

Here is an argument by substitution: \begin{aligned} T(n) &= 3T(n/2)+2n \\&= 3(3T(n/4)+n)+2n \\&= 3(3(3(T(n/8)+n/2)+n)+2n \\&= \cdots \\&= 3^kT(n/2^k)+\sum_{i=0}^{k-1}{2n\left(\frac{3}{2}\right)^i} \\&= 3^kT(n/2^k)+2n\frac{\left(\frac{3}{2}\right)^k-1}{\left(\frac{3}{2}\right)-1} \\&= 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) &= 3^{log_2n}T(1)+4n\left(\frac{3}{2}\right)^{log_2n}-4n \\&= n^{log_2{3}}+4n\cdot n^{log_2\frac{3}{2}}-4n \\&= \cdots \\&= 5n^{log_2{3}}-4n \\&\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$$.