Asymptotic analysis: proof that any quadratic equation asymptotically tight bounds $n^2$

Question

I trying to understand this assertion:

$an^2 + bn + c \in \Theta(n^2)$

By definition of $\Theta$ is possible to assume:

$0 \le c_1 n^2 \le an^2 + bn + c \le c_2 n^2$

$n \ge n_0$

So one valid proof is:

$c_1 = \frac{a}{4}$

$c_2 = 7\frac{a}{4}$

$0 \le \frac{a}{4}n^2 \le an^2 + bn + c \le 7\frac{a}{4} n^2$

$n_0 = 2 \max\left(\frac{|b|}{a}, \sqrt\frac{|c|}{a}\right)$

How can I achieve this answer? I need to understand mainly the $n_0$ statement.

Formula simulated in Geogebra 6

Answer 1

To show that $an^2+bn+c\in \Theta(n^2)$ we first should notice that this is only true if $a\not=0$, otherwise it belongs to $O(n)$.

Next, recall from definition what this means: $$ \frac{an^2+bn+c}{n^2} $$ does not blow up to $\infty$ or $-\infty$ as $n\to\infty$, nor does it tend to $0$.

Simplifying the fraction we get $$ \frac{an^2+bn+c}{n^2}=a+\frac{b}{n}+\frac{c}{n^2}. $$ The latter two terms tend to $0$ as $n\to\infty$, leaving just the $a$ as the limit, which is finite and non-zero.

Answer 2

$$ c_1 n^2 \le an^2 + bn + c \le c_2 n^2\iff c_1 \le a +\frac bn +\frac c{n^2} \le c_2.$$

It is obvious that the function in the middle is bounded for $n>0$ and for any $n_0$ you can find suitable $c_1,c_2$.