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

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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.