3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you, by this doesn't really answer the questions I asked. Also, a quadratic function has by definition $a \ne 0$. $\endgroup$ – Alex R Oct 17 at 20:35
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 17 at 20:36
  • $\begingroup$ 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$. $\endgroup$ – Alex R Oct 17 at 20:46
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 17 at 20:48
2
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.