Show Time $T(n) = Θ(n^3)$

Question

I have to show that : $$T(n) = Θ({n^3})$$

---

We have this recursive function :

$$T(n) = 8T(n/2) + n^2, n>=2$$

also we know that $$T(1) = 1$$

And it says that there is a "replacement method" to do that.

---

EDIT

---

If I say $$n = 2^k, k≥1$$

then T(n) will become... $$T(2^k) = 8T(2^k/2) + (2^k)^2$$

$$T(2^k+1) = 8T(2^(k+1) + (2^k+1)^2$$

and I can't get to Θ(n^3)

Answer 1

The point is to use cancellation.

$$ T(2^k) = 2^3\,T(2^{k-1}) + 2^{2(k)}\quad. $$ You want to eliminate the $2^3\,T(2^{k-1})$ so you find an expression for it:

$$ T(2^{k-1}) = 2^3\,T(2^{k-2}) + 2^{2(k-1)} \implies 2^3\,T(2^{k-1}) = 2^{6}\,T(2^{k-2}) + 2^{2k+1} \quad. $$ Continuing in this manner, we have

$$\begin{align} T(2^k) &= 2^3\,T(2^{k-1}) + 2^{2k} \\ 2^3\,T(2^{k-1}) &= 2^{6}\,T(2^{k-2}) + 2^{2k+1} \\ 2^6\,T(2^{k-2}) &= 2^{9}\,T(2^{k-3}) + 2^{2k+2} \\ &\cdots \\ 2^{3(k-1)}\,T(2^{k-(k-1)}) &= 2^{3k}\,T(2^{k-k}) + 2^{2k+(k-1)} \\ \end{align} $$ Sum up the columns and terms on the left hand side cancel almost all terms on the right hand side. And you arrive at

$$\begin{align} T(2^k) &= 2^{3k}T(2^0) + 2^{2k}\sum_{i=0}^{k-1} 2^i \\ &= 2^{3k}T(1) + 2^{2k}(2^k-1) \\ &= 2n^3 - n^2 \quad=\quad \Theta(n^3)\quad. \end{align} $$

Answer 2

Let $S(k)=T(2^k)/8^k$. Then $S(k)=S(k-1)+1/4^k$ for $k\geqslant1$ and $S(0)=1$ hence, for every $k\geqslant0$, $$1\leqslant S(k)\leqslant1+1/4+1/4^2+\cdots\leqslant2. $$ Thus, for every $k\geqslant0$, $(2^k)^3\leqslant T(2^k)\leqslant2\cdot(2^k)^3$.

For every $n\geqslant1$ there exists $k\geqslant0$ such that $2^k\leqslant n\leqslant 2^{k+1}$ hence, if the sequence $T$ is nondecreasing then $$T(n)\leqslant T(2^{k+1})\leqslant16\cdot(2^k)^3\leqslant16\cdot n^3, $$ and $$T(n)\geqslant T(2^{k})\geqslant(2^k)^3\geqslant\frac18\cdot n^3. $$ In particular, $$T(n)=\Theta(n^3).$$