2

As a deeply enthusiastic prospective undergraduate student, there are is a fact that i'm still to completely understand about the big $O$ notation, namely:

Let $f(x), g(x) \neq x$ be nonconstant differentiable functions with $f(x), g(x) = O(x)$. Does it necessarily follow that

$\dfrac{f(x) - x}{f(x) - g(x)} = \dfrac{O(x) - x}{O(x)} = O(1)$ ?

My attempt:

Since $f(x), g(x) = O(x)$, it follows that $f'(x), g'(x) =O(1)$, hence by the L'-Hopital Rule, we have $\lim_{x \to \infty} \dfrac{f(x) - x}{f(x) - g(x)} = \dfrac{O(1)}{O(1)}=O(1)$, as required ?

David K
  • 98,388
User1
  • 1,841
  • 2
    A function being $O(x)$ imposes no limitation on its derivative. For example $x\sin x$ is $O(x)$ but there is no such conclusion for its derivative. – Mikhail Katz Feb 04 '16 at 13:45
  • Try $x \sin x^2$ instead. – David K Feb 04 '16 at 13:50
  • I am disturbed by your attempt to do "arithmetic" with "O". O(1) is not a number of other object for which O(1)- x or O(1)/O(1) are defined. Saying f(x)= O(x) is just saying that, in the limit (as x goes to some value or infinity or negative infinity) f(x)/x= k or, equivalently, f(x)= kx for some non-zero k. Since g(x)= O(x), it follows that (in the limit) g(x)= px for some non-zero p. So f(x)- x= kx- x= (k-1)x and f(x)- g(x)= kx- px= (k- p)x. (f(x)- x)/(f(x)- g(x))= (k-1)/p. What if k= 1? Also it does not follow that f and g are differentiable so you cannot use L'Hopital. – user247327 Feb 04 '16 at 13:50
  • 1
    @user247327, i guess that's why i'm asking. – User1 Feb 04 '16 at 13:52
  • The notation $f(x)=O(x)$ is somewhat misleading. The real relationship is more like $f(x)\in O(x)$. Here's another example why you should not try to do arithmetic on big-O classes: http://math.stackexchange.com/q/1618659/139123 – David K Feb 04 '16 at 14:03

1 Answers1

3

For an explicit counterexample, consider $f(x) = 2x$ and $g(x) = 2x + 1/x$. Both are $O(x)$. Then $f(x) - x = x$ and $f(x) - g(x) = 1/x$. So then $$\frac{f(x) - x}{f(x) - g(x)} = \frac{x}{1/x} = x^2$$ which is much larger than $O(x)$!

This is a good intuition-building exercise on why you must be careful when using multiple big-oh expressions. For instance, having a big-oh result for a function in a denominator is not particularly useful for making upper bounds, as one wants lower bounds for functions in denominators to generate upper bounds for the overall expression.

davidlowryduda
  • 91,687