I am trying to prove the following through Big Oh induction:
$T(n) = 3T(\frac{n}{2}) + n^2\quad when\quad n\geq2\quad prove\quad T(n)\in O(n^2)\quad$ with a base case of $\quad T(1) = 1$
I've taken the following steps:
Base Case: $n=2 \quad T(2) = 3T(\frac{2}{2}) + 2^2 = 3*1+4 = 7 \leq c*2^2 = c*4$
Where I can pick c to make this true $7 \leq c*4$
Inductive Step:
Assume $T(k) \leq c*k^2 \quad$ for all $\quad k \leq n$
$T(n) = 3T(\frac{n}{2})+n^2 \leq 3(c*\frac{n^2}{2^2})+n^2 = c*n^2*\frac{3}{4}+n^2 $
Now I know I need to get this to be $\quad \leq c*n^2 \quad$ but I don't know how to negate the $\quad \frac{3}{4} + n^2 \quad$ that is left over. I don't think I can just say "when $\quad c \geq \frac{3}{4}+n^2$". What are your suggestions?
Best Answer
Remember you just need to prove that $T(n)\le cn^2$ holds for some $c$. You can choose whatever $c$ you want. In order to get $$ \frac34 c n^2+n^2\le cn^2, $$ all you need is $$ \frac34 c+ 1\le c, $$ so choose any $c$ for which that is true.