asymptotic tight bound for quadratic functions

问题:

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 ?

回答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.

回答2:

The idea is to (for big enough n) "trap" the function of interest between two "pure" growth functions (that have only a single constant of proportionality). In this figure two quadratic functions (drawn in red and blue) are trapped between two pure growth functions (drawn in black), and the minimum possible value of n₀ in each case is indicated.

So once you've picked your values of c₁ and c₂, you can find the value of n₀ by intersecting your function with the two pure growth functions and taking the rightmost intersection.

But you don't care about the getting smallest possible value for n₀ — we're doing asymptotics here, so any big enough value will do — so you can use approximations to get an upper bound on it.

See davin's answer for how to get the upper bound for n₀ into the form given in CLRS.

回答3:

c1 and c2 can be chosen arbitrarily, as long as 0 < c1 < a and a < c2 < infinity. n0 is then calculated from this, so that the inequality 0 <= c1*n^2 <= an^2 + bn + c <= c2*n^2 is satisfied for all n>=n0.

回答4:

To prove that any polynomial f(n)=a0+a1*n+a2*n^2+a3*n^3+...+am*n^m is theta(n^m), follow two simple steps. step 1. show that f(n) is bigOh(n^m) step 2. show that f(n) is bigOmega(n^m)

If both the above conditions hold good, then definitely f(n) is bigTheta(n^m).

This is a generalization. By putting m=2, you get f(n) is bigTheta(n^2) Simple.. isn't it?

回答5:

well its easy 1.c1<=a + b/n + c/n^2 Now here a is >0 while b,c are either positive or negative Now we must choose value of n such that b/n + c/n^2 never exceeds a in RHS of above eqution cause else it will become negative and so will c1. but by definition c1 is a positive constant

So we want to make sure a>b/n+c/n^2

if we choose n=2*max(|b|/a, sqrt(|c|/a) ) we will get b/n + c/n^2 as an expression whose value is less than a/2+a/4.

thus a+b/n+c/n^2 will have maximum value as a+a/2+a/4 and minimum value as a-(a/2+a/4) which is nothing but values of c2 and c1.

c1=a-a/2-a/4= a/4 c2=a+a/2+a/4= 7a/4

This concept can be extended to any values for any polynomial..

cheers!!!

回答6:

P(n) = an² + bn + c = an²( 1 + b / ( an ) + c / ( an² )) = an²( 1 ± ( | b | / a ) / n ± ( √( | c | / a ) / n )²
so if we take for example q = max( | b | / a, √( | c | / a )) than
P(n) ≤ an²( 1 + ( q / n ) + ( q / n )² ) and if we take n₀ = q than we'll get the second constant
c₂ = 3a analogically for the lower bound