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.