0
$\begingroup$

I'm reading "Introduction to Algorithms" 3rd edition by Cormen, Leiserson, Rivest, Stein Page 46. The authors place formal upper and lower bounds on a function which is quadratic. Can anyone explain where the values for $c_1$, $c_2$ and $n_0$ are taken? I'm also confused why the $max$ function is used and it's parameters.

Text

$\endgroup$
1
$\begingroup$

The values of $c_1$ and $c_2$ are pulled out of thin air. Their actual values don't matter except for the property that $$0<c_1\leq a\leq c_2$$

The value of $n_0$ also doesn't matter except for the property that $$n>n_0\implies c_1n^2\leq an^2+bn+c\leq c_2n^2$$

This implication is equivalent to saying that the interval $n\geq n_0$ is inside the set of solutions of the system of inequalities $$\begin{cases}(a-c_1)n^2+bn+c&\geq0\\(c_2-a)n^2-bn-c&\geq0\end{cases}$$

So, they solved the system of inequalities $$\begin{cases}\frac{3a}{4}n^2+bn+c&\geq0\\\frac{3a}{4}n^2-bn-c&\geq0\end{cases}$$

You can see now that the concrete values of $c_1$ and $c_2$ were chosen such that the two inequalities in the system are nearly the same, except for the sign of the coefficients. The two are quadratic polynomials with positive leading term. They are going to be non-negative outside the interval formed by their roots. So, for the interval $n>n_0$ to be inside, we just need to take $n_0$ to be a bound from above of the absolute value of the roots.

There are many known bounds of the roots in terms of the coefficients. It looks like they took this bound by Lagranges. Although $2\max\left(\frac{|b|}{a},\sqrt{\frac{|c|}{a}}\right)$ would be the bound for the roots of the polynomial $an^2+bn+c$ and we have instead $\frac{3}{4}an^2+bn+c$. The bound would be instead $2\max\left(\frac{4|b|}{3a},\sqrt{\frac{4|c|}{3a}}\right)$, which is somewhat larger.

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