Question

Show that f(x) = x^2+2x+1 is O(x^2).
|f(x)|k. How do I find the witnesses, C and K for that function?

Answer 1

Remove those ugly absolute value signs, because these functions are nonnegative anyway.
If I'm not missing something, you have to prove that whenever \(x > k\), you can find a constant \(C\) such that\[x^2 + 2x + 1 < Cx^2\]I hope I'm not missing anything because I haven't studied this.

Answer 2

well, let's see.\[(C-1)x^2 + 2x + 1 > 0\]the left side is an upward parabola that has no roots. so the discriminant is negative.\[4 - 4(C-1) < 0 \Rightarrow C > 1 \]So yeah that's pretty reassuring.

Answer 3

You can also do it like this.

|f(x)| is O(x^2) if
|f(x)|<|cx^2| for some x>k

which means
x^2+2x+1<cx^2 for all x real.
divide by x^2
1+2/x+1/x^2 < c
for k=1,
1+2+1 <c
So by setting k=1 and c=5, we have
f(x)<cx^2 for all x>1.

Notice that c and k are not exactly independent.

Answer 4

what happened after dividing both sides by x^2

Answer 5

when x=1, 1+2/x+1/x^2=4
The left-hand side becomes a decreasing function, so that we're sure that the LHS is less than C as x increases.