Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I have the following algorithm runtime: $T(1) = b $ for some positive constant. Otherwise, $T(n)=8T(\frac n 2) + 100n^2$ I am trying to prove that it is $\Theta(n^3)$ by induction. I proved that it is $\Omega(n^3)$ using constant $c=\frac b 2$ and $n_0=1$.
I am trying to prove that it is $O(n^3)$ by induction (without the master theorem) and I get stuck at the induction step. I am using $c=b$ for the induction basis.
Any assistance will be welcomed.
Let's prove that $T(n)\leq (100+b)n^3-100n^2$
For $n=1$ we have $T(1)=b=(100+b)\cdot1^3-100\cdot 1^2$.
Assume that $T(k)\leq (100+b)k^3-100k^2$ for all $1\leq k< n$. Then $$\begin{align} T(n)&=8T(n/2)+100n^2\\ &\leq8\left[(100+b)(n/2)^3-100(n/2)^2\right]+100n^2\\ &=(100+b)n^3-200n^2+100n^2\\ &=(100+b)n^3-100n^2 \end{align} $$
