1

How would I find the witnesses $C$ and $k$ such that $f(x)$ is $O(x)$?

What I tried was $$(x^4+x^2+1)/(x^3+1) ≤ (x^4+x^4+x^4)/(x^3+x^3) = (3/2)x $$ for values $x>1$. $C = 3/2, k = 1$

Is this right?

Matthew Conroy
  • 11,234
Kris
  • 131
  • 1
    Do you mean $O(x)$ as $x \to \infty$? – Antonio Vargas Nov 18 '13 at 22:55
  • Yes, as x -> (infinity) – Kris Nov 18 '13 at 22:56
  • 1
    What are "witnesses"? – Bennett Gardiner Nov 18 '13 at 23:01
  • 1
    In your attempt, it is not true that $1/(x^3+1) \leq 1/(x^3 + x^3)$. It is true, however, that $1/(x^3 + 1) \leq 1/(x^3 + 0)$. – Antonio Vargas Nov 18 '13 at 23:08
  • "Witness" is the logic term used to refer to the value used to satisfy a $\exists$ statement. Kris your argument is correct, but you probably want to be more explicit and show exactly how C and k fit into the definition of $f \in O(x)$, I'm guessing you mean $\exists k, C, \forall x \ge k, f(x) \le Cx$ – DanielV Nov 19 '13 at 00:42
  • @DanielV, The argument is not correct... Or, more precisely, it is correct, but only accidentally. – Antonio Vargas Nov 19 '13 at 03:53
  • @AntonioVargas Well I'm giving him the benefit of the doubt that he intended to use the definition correctly but didn't fill in all the details; it's hard for me to say for sure. – DanielV Nov 19 '13 at 10:03

3 Answers3

1

We have

$$ f(x)= \frac{x^4 + x^2 +1 }{x^3 +1} \leq C x, $$

for $x \geq \sqrt{\frac{C}{3(C-1)}}$ and $C>1$.

Berkheimer
  • 2,086
  • 17
  • 31
0

Hint: The degree of the numerator is $4$, while the degree of the denominator is $3$. The degree of $O(x)$ is $4-3=1$.

Ahaan S. Rungta
  • 7,706
0

$$\dfrac{x^4+x^2+1}{x^3+1} = \dfrac{(x^2+x+1)(x^2-x+1)}{(x+1)(x^2-x+1)} = \dfrac{x^2+x+1}{x+1} = x + \dfrac1{x+1}$$ Now you should be able to conclude what you want.