Originally Posted by

**JTG2003** One more thing. What is a "witness"?

From the book:

"Consequently, we can take C = 4 and k = 1 as witnesses to show that f(x) is O($\displaystyle x^2$). That is, f(x) = $\displaystyle x^2 + 2x + 1 < 4x^2$ whenever x > 1."

Any idea what they're referring to?

I lied.. another question:

"Alternatively, we can estimate the size of f(x) when x > 2. When x > 2, we have $\displaystyle 2x \leq x^2$ and $\displaystyle 1 \leq x^2 $. Consequently, if x > 2, we have

$\displaystyle 0 \leq x^2 + 2x + 1 \leq x^2 + x^2 + x^2 = 3x^2 $

It follows that C=3 and k=2 are also witnesses to the relation f(x) is O(x^2)."

Again with the witnesses ...

Are the constants always integers?