From: Competitive Enterprise Institute <cei@access.digex.net>
Date: Fri, 17 Jun 94 22:57:36 PDT
To: Jeff Gostin <jgostin@eternal.pha.pa.us>
Subject: O(f(x))
In-Reply-To: <940617160624Y4Wjgostin@eternal.pha.pa.us>
Message-ID: <Pine.3.89.9406180153.A7665-0100000@access1.digex.net>
MIME-Version: 1.0
Content-Type: text/plain


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