I am reading the book "Introduction to Algorithms", 3rd Edition, by Cormen, Leiserson, Rivest and Stein, and on page 46, they write the following:
"[…] consider any quadratic function $f(n)=an^2+bn+c$, where $a$, $b$, and $c$ are constants and $a>0$. Throwing away the lower-order terms and ignoring the constants yield $f(n)=\Theta(n^2)$. Formally, to show the same thing, we take the constants $c_1=a/4$, $c_2=7a/4$, and $n_0=2\max\left(|b|/a,\sqrt{|c|/a}\right)$. You may verify that $0\leq c_1n^2\leq an^2+bn+c\leq c_2n^2$ for all $n\geq n_0$."
The first thing that made me wonder was the choice of constant $n_0$, but since the authors' definition of $\Theta$ requires that all involved functions are non-negative beyond $n_0$, this constant must be chosen to be at least the biggest root of $f$ (see below).
The second thing is that I can't seem to derive these inequalities with the given constants. Can you help me with this?
Here is the derivation that $n_0$ is larger than the biggest root of $f$. Since $a>0$, the function $f$ will definitely be positive from some point and onwards. If $b^2-4ac<0$, we have $f(n)>0$ for all $n$, so assume $b^2-4ac\geq 0$. Then the larger root of $f$ is
\begin{align*}
\frac{-b+\sqrt{b^2-4ac}}{2a} &= \frac{-b}{2a}+\sqrt{\left(\frac{b}{2a}\right)^2-\frac{c}{a}}\\
&\leq \frac{|b|}{2a}+\sqrt{\left(\frac{b}{2a}\right)^2+\frac{|c|}{a}}\\
&\leq \frac{|b|}{2a}+\sqrt{\left(\frac{b}{2a}\right)^2}+\sqrt{\frac{|c|}{a}}\\
&= \frac{|b|}{a}+\sqrt{\frac{|c|}{a}}\\
&\leq 2\max\left(\frac{|b|}{a}, \sqrt{\frac{|c|}{a}}\right).
\end{align*}
Let $n\geq n_0$. To show that e.g. $an^2/4\leq an^2+bn+c$, my idea was to show that $(3a/4)n^2+bn+c\geq 0$ by showing that $n_0$ is also at least the largest root of this quadratic, but my inequalities are not tight enough.
Best Answer
Why not go for a direct proof... So, $n_0=2\max\left\{|b|/a,\sqrt{|c|/a}\right\}$, in particular, $n_0\geqslant2|b|/a$ and $n_0\geqslant2\sqrt{|c|/a}$, thus, $b\geqslant-\frac12an_0$ and $c\geqslant-\frac14an_0^2$.
If $n\geqslant n_0$, then $bn\geqslant-\frac12an^2$ and $c\geqslant-\frac14an^2$ hence $f(n)\geqslant an^2-\frac12an^2-\frac14an^2=\frac14an^2$.
Thus, if $n_0>0$, then $f(n)>0$ for every $n\geqslant n_0$. Finally, to be complete, consider that if $n_0=0$, that is, if $b=c=0$, then $f(n)=an^2>0$ for every $n\geqslant1$.