- #1
reef
- 6
- 0
I'm not really sure which section to post this in. I'm having trouble establishing witnesses for big-O functions. Basically I'm wondering if you are looking to solve the inequality for the lowest possible value of k, such that x > k.
Here's an example of what I'm talking about.
Eg. Determine whether f(x) is O(x^2) given the function f(x)=17*x+11.
|f(x)|<=C*|g(x)| where x>k.
|(17*x+11)|
=17*x+11
<=17*x+x where x>11
=18*x
<=x^2 where x>18
Therefore, f(x) is O(x^2) with witnesses C=1 and k=18.
My friend from class tells me that there are multiple correct solutions, but the answer given to me by my instructor is as follows:
|f(x)|<=17*x^2+11*x^2 where x>1
=28*x^2
Therefore, f(x) is O(x^2) with witnesses C=28 and K=1.
Any help/insight would be appreciated. This isn't a homework thread.
Here's an example of what I'm talking about.
Eg. Determine whether f(x) is O(x^2) given the function f(x)=17*x+11.
|f(x)|<=C*|g(x)| where x>k.
|(17*x+11)|
=17*x+11
<=17*x+x where x>11
=18*x
<=x^2 where x>18
Therefore, f(x) is O(x^2) with witnesses C=1 and k=18.
My friend from class tells me that there are multiple correct solutions, but the answer given to me by my instructor is as follows:
|f(x)|<=17*x^2+11*x^2 where x>1
=28*x^2
Therefore, f(x) is O(x^2) with witnesses C=28 and K=1.
Any help/insight would be appreciated. This isn't a homework thread.