Asymptotic runtime of recursive algorithm uisng subsitution method

Question

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

• Steven: The solution can't be $O(n \log n)$. In fact, it must be $\Omega(n^c)$ for some $c>1$.
• Watercrystal: 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.

Answer 1

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$.