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

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?

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.$$

• Thank you, by this doesn't really answer the questions I asked. Also, a quadratic function has by definition $a \ne 0$. – Alex R Oct 17 '19 at 20:35
• It answers the question you should have asked, which is: why are eventually positive quadratics in $\Theta(n^2)$. I suggest focusing on that rather than on immaterial details such as what is the minimal (or rather, infimal) $n_0$ which works for the definition. – Yuval Filmus Oct 17 '19 at 20:36
• Can you recommend a way of finding such a minimal solution? I really want to understand how the authors came up with that value for $n_0$. – Alex R Oct 17 '19 at 20:46
• There is no minimal $n_0$. If the quadratic has a root, then any $n_0$ which is strictly larger than the largest root would work (so any $n_0 > \frac{-b+\sqrt{b^2-4ac}}{2a}$). If the quadratic has no roots, then any $n_0$ would work. – Yuval Filmus Oct 17 '19 at 20:48

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.