Given that $T(n) = n^2 + bn + d$ then it's $O(n^2)$ if I can prove that: $O(n^2) = \{T(n): \text{there exist positive constants } c, n_0 \text{ such that } \forall n \geq n_0, 0 \leq T(n) \leq cn^2 \}$

So I was going to try and prove this using induction where

$Let:\ c = 2bd, n_0 = 2$

$\text{Base Case} (n = n_0):$ $$n^2 + bn + d \leq cn^2$$ $$4 + 2b + d \leq 8bd$$ $$\frac{1}{2bd} + \frac{1}{4d} + \frac{1}{8b} \leq 1$$

...and I can continue to do the rest, but I was looking at the base case and I wasn't sure how to prove that it is true if I don't know what $b$ and $d$ are.

For example, if they're both $0.01$ then it's clearly not true, and I'm not sure how to proceed. Could someone explain this to me?

  • 1
    $\begingroup$ I'm not sure induction is the easiest way to go here. You can just use $n^2+bn+d \leq (1+b+d)n^2$ for $n \geq 1$. $\endgroup$ – Yuval Filmus Nov 29 '17 at 16:43
  • $\begingroup$ @YuvalFilmus wouldn't you still need induction to prove that fact? I know it's intuitively correct $\endgroup$ – john Nov 29 '17 at 18:23
  • 1
    $\begingroup$ Induction is completely unnecessary. Do you need induction to prove that $1+1=2$? Proving $n+n=2n$ is no different. $\endgroup$ – Yuval Filmus Nov 29 '17 at 18:25
  • $\begingroup$ Choosing $c$ in terms of $b$ and $d$ looks a bad idea. (In your example, what if exactly one was negative?) You are not required to find or prove tight bounds: start with $c$ = 10. $\endgroup$ – greybeard Nov 30 '17 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.