asymptotic tight bound for quadratic functions

user_317283 0
Viewed 5711

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

f(n) = an2 + bn + c

they said

Suppose we take the constants c1 = a/4, c2 = 7a/4, and n0 = 2·max(|b|/a, √(|c|/a)).
Then 0 ≤ c1n2 ≤ an2 + bn + c ≤ c2n2 for all n ≥ n0.
Therefore f(n) is Θ(n2).

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 ?

asymptotic-complexity clrs algorithm
6 Answers

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?

user_29990010
Related