asymptotic tight bound for quadratic functions

Question

In CLRS (Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein), for a function

f(n) = an² + bn + c

they said

Suppose we take the constants c₁ = a/4, c₂ = 7a/4, and n₀ = 2·max(|b|/a, √(|c|/a)).
Then 0 ≤ c₁n² ≤ an² + bn + c ≤ c₂n² for all n ≥ n₀.
Therefore f(n) is Θ(n²).

But they didn't specify how values of these constants came ?
I tried to prove it but couldn't.
Please tell me how these constants came ?

Answer 1

There's nothing special about those particular constants (other than the fact that in context of a certain n value they will satisfy the theta-ness of f). No magic. If you can find other positive constants whereby the relation holds that is just as valid (in fact, c1 can be ka for any 0<k<1). Although since they're there, let's analyse c1:

We need it to satisfy the following inequality:

c1*n^2 <= an^2 + bn + c

Let's take their value: c1 = a/4. For what n can we guarantee that the inequality holds? We could solve:

a/4*n^2 <= an^2 + bn + c
<==> 0 <= 3a/4*n^2 + bn + c

The quadratic has solutions at (-b +- sqrt(b^2-3ac)) / (3a/2), only the positive of which is of any interest since we have a positive leading coefficient polynomial, so we require n > 2 * (sqrt(b^2-3ac) - b) / 3a which is well defined assuming b^2 >= 3ac (and if not, then the quadratic is positive definite, which is even better, since its >=0 everywhere and the inequality holds for all n). I should point out that this is a valid solution, although we'll do a bit more work until we arrive at the book's representation.

We can split our analysis into 2 cases. First, let's assume |b|/a >= sqrt(|c|/a). So we can bound from above the inside of the sqrt(...) with 4b^2, and require n > 2/3 * [sqrt(4b^2)-b]/a which can be upper bounded by 2/3 * 3|b|/a = 2|b|/a.

Second case, let's assume |b|/a < sqrt(|c|/a). So we can bound from above the inside of the sqrt(...) with 4a|c|, and require n > 2/3 * [sqrt(4a|c|)-b]/a which can be upper bounded by 2/3 * 3*sqrt(a|c|)/a = 2sqrt(|c|/a).

So in each case we see that when we take max(|b|/a, sqrt(|c|/a)) our inequality holds when n > 2 * max

Similarly for c2.