How to show that every quadratic, asymptotically nonnegative function $\in \Theta(n^2)$

Question

In the book CLRS the authors say that every quadratic, asymptotically nonnegative function $f(n) = an^2 + bn + c$ is an element of $\Theta(n^2)$. Using the following definition

\begin{align*} \Theta(n^2) = \{h(n) \,|\, \exists c_1 > 0, c_2 > 0, n_0 > 0 \,\forall n \geq n_0: 0 \leq c_1n^2 \leq h(n) \leq c_2n^2\} \end{align*}

the authors write that $n_0 = 2*\max(|b|/a, \sqrt{|c|/a})$.

I have difficulties proving that the value of $n_0$ is indeed that value.

We know that $a \ge 0$ because otherwise $f$ would not be asymptotically nonnegative. Calculating the roots of $f$ gives us:

\begin{align*} n_{1/2} &= \frac{-b \, \pm \, \sqrt{b^2 - 4ac} }{2a} \\ &\leq \frac{|b| + \sqrt{b^2 - 4ac} }{a} \end{align*}

The case $c \ge 0$ gives us:

\begin{align*} \frac{|b| + \sqrt{b^2 - 4ac} }{2a} \leq \frac{|b| + \sqrt{b^2} }{a} = 2\frac{|b|}{a} \end{align*}

which is two times the first argument of the $\max$ function.

But what about the case $c < 0$? How can we find an upper bound for that? Where does the value $\sqrt{|c|/a}$ actually come from?

Answer 1

CLRS is wrong. For example, the function $0n^2+0n+0$ is asymptotically nonnegative but doesn't belong to $\Theta(n^2)$. Changing "nonnegative" to "positive" doesn't help: you can consider $0n^2+0n+1$. Even requiring the function to be nonconstant doesn't help: consider $0n^2+1n+0$.

Here is a statement which is correct: if $a > 0$ then $an^2+bn+c = \Theta(n^2)$. Indeed, when $n \geq 2\frac{|b|+|c|}{a}+1$ then $$ |(an^2 + bn + c) - an^2| = |bn+c| \leq |b|n+|c| \leq (|b|+|c|)n < \tfrac{1}{2} an^2, $$ and so $$ \tfrac{1}{2} an^2 \leq an^2 + bn + c \leq \tfrac{3}{2} an^2. $$

Answer 2

So I actually found the answers I was looking for. The case $c \ge 0$ is already handled in the question above. For the case $c < 0$ we have:

\begin{align} n_{1/2} &= \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} \\ &\le \frac{|b| + \sqrt{b^2 - 4ac}}{a} \\ &\le \frac{|b| + \sqrt{b^2} + \sqrt{-4ac}}{a} \\ &= \frac{2|b| + \sqrt{4a|c|}}{a} \\ &= \frac{2|b| + 2\sqrt{\frac{a^2|c|}{a}}}{a} \\ &= 2\frac{|b|}{a} + 2\sqrt{\frac{|c|}{a}} \\ &\le 2\max(\{|b|/a, \sqrt{|c|/a}\}) \\ &= n_0 \end{align}

This value for $n_0$ includes the case $c \ge 0$. If $f$ doesn't have any roots, we can instead choose $n_0 = 1$.

For the constants $c_1, c_2$ the authors gave us the values $c_1 = a/4$ and $c_2 = 7a/4$. To check that these are correct we do the following:

Since $n \ge 2|b|/a$ and $n \ge 2\sqrt{|c|/a}$, we know that: \begin{alignat}{3} && \frac{1}{2} &\ge &\frac{|b|}{an} \quad&\text{and}\quad &\frac{1}{4} \ge &\frac{|c|}{an^2} \\ &&-\frac{1}{2} &\le -&\frac{|b|}{an} \quad&\text{and}\quad -&\frac{1}{4} \le -&\frac{|c|}{an^2} \end{alignat}

This gives us

\begin{alignat}{2} &\frac{1}{4} = 1 - \frac{1}{2} - \frac{1}{4} \le 1 - \frac{|b|}{an} - \frac{|c|}{an^2} \le 1 + \frac{b}{an} + \frac{c}{an^2} \\ \text{and therefore}\quad &\frac{a}{4}n^2 \le an^2 + bn + c \end{alignat}

and

\begin{alignat}{2} &1 + \frac{b}{an} + \frac{c}{an^2} \le 1 + \frac{|b|}{an} + \frac{|c|}{an^2} \le 1 + \frac{1}{2} + \frac{1}{4} = \frac{7}{4} \\ \text{and therefore}\quad &an^2 + bn + c \le \frac{7a}{4}n^2 \end{alignat}

which shows that the values $c_1 = a/4$ and $c_2 = 7a/4$ are indeed correct.