1

I need an explanation of this section of Chapter 3 in Introduction to Algorithms.

As an example, consider any quadratic function f(n) = an² + bn + c, where a, b, and c are constants and a > 0. Throwing away the lower-order terms and ignoring the constant yields f(n) = Θ(n²). Formally, to show the same thing, we take the constants c₁ = a/4, c₂ = 7a/4, and n₀ = 2 · max(|b|/a, √(|c|/a)). You may verify that 0 ≤ c₁n² ≤ an²+bn+c ≤ c₂n² for all n ≥ n₀.

It makes complete sense to me that any quadratic function will be Θ(n²) because you drop the lower order terms and the coefficient of the highest order term. But, in this proof, why are these constant values chosen for c₁, c₂, and n₀? They seem arbitrary but perhaps there is something I'm missing. I generally understand the definition of Θ but not this proof as it relates to quadratic functions.

ruakh
  • 175,680
  • 26
  • 273
  • 307
user3509054
  • 92
  • 2
  • 2
    Does this answer your question? [asymptotic tight bound for quadratic functions](https://stackoverflow.com/questions/6690795/asymptotic-tight-bound-for-quadratic-functions) – Muhteva Sep 22 '21 at 07:58

1 Answers1

0

The parameters seem arbitrary, because they are. The definition only says that such parameters exists and normally there are a lot of parameters that work. Just choose a c and calculate a n for that specific c.

AbcAeffchen
  • 14,400
  • 15
  • 47
  • 66