O(f(x))

[Competitive Enterprise Institute <cei@access.digex.net>]

On Fri, 17 Jun 1994, Jeff Gostin wrote:

>      Well, I don't know what it means. If you'd care to tell me, even in
> mail, I'd like to know. I've been following this thread with interest, but
> I don't pretend to follow this X(f(y)) notation all the time. I understand
> that it means we are applying function X to the result of f(y)... Anyone
> who's passed Trig or Elem. Functions does. I don't understand what
> function O(x) represents.

The way *I* learned it was like this:
g(x) = o(f(x)) means that g(x)/f(x) -> 0 (as x goes to some specified limit)
g(x) = O(f(x)) means that |g(x)/f(x)| is bounded (as x goes to some limit)

In other words: a function that is o(f(x)) is of lower order than f(x), 
while a function that is O(f(x)) is of no higher order than f(x).

						- Sasha Volokh