First Order Recursion: $T(0) = 0$ and $T(n) = 3T(n/2) + n, n \geq 1$

Question

Well I got this problem:

$$T(0) = 0$$ $$T(n) = 3T(n/2) + n, n \geq 1$$

I simplified the equation to the following.

$$3^iT(n/2^i) + 2n((3/2)^i - 1)$$

From this point I am confused how to solve. Thanks for any help.

Answer 1

Since $n$ is integer, what is $T(n)$ when $n == 1$?

Other than that, let $n = 2^m$ we have,

$$ T(2^m) = 3T(2^{m-1}) + 2^m, m \ge 0 $$

Let $f(m) = T(2^m)$,

$$ f(m) = 3f(m-1) + 2^m $$

=>

$$ f(m) + 2^{m+1} = 3(f(m-1) + 2^m) $$

If you can solve $$g(m) = f(m) + 2^{m+1} = 3g(m)$$ you will got the idea.

It looks like a high school math question though.

Answer 2

I claim that $\boxed{T(n) = \Theta(n^{\log_2 3})}$. This magical claim came from Case 1 of the Master Method. To see this, I will prove it by induction (I'll skip the base case).

Induction Hypothesis: Assume that there exist some $a,b,c,d>0$ such that for all $k<n$, we have: $$ ak^{\log_2 3} + bk \leq T(k) \leq ck^{\log_2 3} - dk $$

It remains to prove that the inequality holds true for $k=n$. Observe that: \begin{array}{rcccl} 3T(n/2) + n &=& T(n) &=& 3T(n/2) + n \\ 3\left[a\left(\dfrac{n}{2}\right)^{\log_2 3} + b\left(\dfrac{n}{2}\right)\right] + n &\leq& T(n) &\leq& 3\left[c\left(\dfrac{n}{2}\right)^{\log_2 3} - d\left(\dfrac{n}{2}\right) \right] + n\\ 3\left[a\left(\dfrac{n^{\log_2 3}}{3}\right) + \left(\dfrac{b}{2}\right)n\right] + n &\leq& T(n) &\leq& 3\left[c\left(\dfrac{n^{\log_2 3}}{3}\right) - \left(\dfrac{d}{2}\right)n \right] + n\\ \left[an^{\log_2 3} + \left(\dfrac{3b}{2}\right)n\right] + n &\leq& T(n) &\leq& \left[cn^{\log_2 3} - \left(\dfrac{3d}{2}\right)n \right] + n\\ \left[an^{\log_2 3} + bn\right] + \left(\dfrac{b}{2} + 1 \right)n &\leq& T(n) &\leq& \left[cn^{\log_2 3} - dn \right] + \left(1-\dfrac{d}{2}\right)n\\ an^{\log_2 3} + bn &\leq& T(n) &\leq& cn^{\log_2 3} - dn\\ \end{array} provided that $d \geq 2$. This completes the induction.