I am very lost right now when it comes to finding witnesses for big O relationships. The problem says the following:
To establish a big O relationship, find witnesses C and k such that
| f(x) | <= C | g(x) | whenever x > k
Determin whether each of these functions is O(x^2)
a) f(x) = 17x + 11
First of all, I am not sure if this is a O(x^2) function. I believe it is not because the function is not quadratic therefore it cannot be a O(x^2) function.
b) f(x) = x^2 +1000
This function is clearly a O(x^2) function. Now as for solving for C and k, I have no idea how to do.
I do not understand what is C and k, and what do they do.
Looking at "| f(x) | <= C | g(x) | whenever x > k"
f(x) is the function given
g(x) is the x^2 in "O(x^2)" right?
so for part b)
x^2 +1000 <= C(x^2)
now if k = 1 x>k so x can be 2 and that gives 1004 <= C*4
so C can be 251?
Thank you for your help!