Hi,

I am a computer science student. In computer science the little-oh
function is defined as (unless I am wrong):
if g(n) is in o(f(n)), then
g(n) < n1 * f(n) for all n>=n2, for two constants n1 and n2 >= 0

(reverse is true also)

I recently bumped in to the following definition for little-oh notation
in a math book (on stochastic processes) :
if g(n) is in o(f(n)) then
lim n->0 g(n)/f(n) = 0

What is the correct little-oh definition? These two seem to contradict
eachother, in the first definition x is in o(x^2) while according to
the second definition we would get x^2 is in o(x).

Please help,
Andersen

From:	Mitch Harris
Subject:	Re: little-oh
Date:	Wed, 19 Jan 2005 10:15:06 +0100

Andersen wrote:
> Hi,
>
> I am a computer science student. In computer science the little-oh
> function is defined as (unless I am wrong):
> if g(n) is in o(f(n)), then
> g(n) < n1 * f(n) for all n>=n2, for two constants n1 and n2 >= 0
>
> (reverse is true also)
>
> I recently bumped in to the following definition for little-oh notation
> in a math book (on stochastic processes) :
> if g(n) is in o(f(n)) then
> lim n->0 g(n)/f(n) = 0
>
> What is the correct little-oh definition? These two seem to contradict
> eachother, in the first definition x is in o(x^2) while according to
> the second definition we would get x^2 is in o(x).

Since these operators tell you about functions asymptotically (for
larger and larger parameters, a better definition is:

lim n->infinity g(n)/f(n) = 0

--
Mitch Harris
(remove q to reply)

From:	Lars Engebretsen
Subject:	Re: little-oh
Date:	Wed, 19 Jan 2005 12:00:27 +0100

Mitch Harris writes:

> Andersen wrote:
>> Mitch Harris wrote:
>>
>>> Since these operators tell you about functions asymptotically (for
>>> larger and larger parameters, a better definition is:
>>>
>>> lim n->infinity g(n)/f(n) = 0
>> This does not define the same set of functions as
>> lim n->0 g(n)/f(n) = 0
>> which is the definition given in the stochastic process book I am
>> using.
>
> Then something weird is going on here.

I may be missing something here, but isn't it just a question of what
limit we are interested in? If we want to say that a function drops to
zero faster than x^2 as x->0 then it seems natural to me to say that
the function is o(x^2) --- which is the second definition above. And
if we want to say that the function grows slower than n as n->infty
it seems natural to say that the function is o(n).

The "order" of some expression tells us what the expression looks like
as we approach a limit; the limit is not written in the actual symbol
(O, o, Omega, omega, Theta) but implied by the context.

/Lars

--
Lars Engebretsen, PhD,

From:	Andersen
Subject:	Re: little-oh
Date:	Wed, 19 Jan 2005 17:17:50 +0100

Lars Engebretsen wrote:
> Mitch Harris writes:
>
> I may be missing something here, but isn't it just a question of what
> limit we are interested in? If we want to say that a function drops to
> zero faster than x^2 as x->0 then it seems natural to me to say that
> the function is o(x^2) --- which is the second definition above. And
> if we want to say that the function grows slower than n as n->infty
> it seems natural to say that the function is o(n).
>
> The "order" of some expression tells us what the expression looks like
> as we approach a limit; the limit is not written in the actual symbol
> (O, o, Omega, omega, Theta) but implied by the context.

I have got lots of replies in this newsgroup and others. Most of them
contradictory. Your answer is the only one which makes sense, so from
the context you should infer which definition or limit that is implied.
If it involves real numbers, such as
"e^x = 1 + x/1! + x^2/2! + o(x^3)", it implies a definition where the
limit goes to 0. If the context involves natural numbers, such as number
of iterations in a loop, it is likely to imply a definition where the
limit goes to infinity. Right?

thanks,
Andersen

From:	Andersen
Subject:	Re: little-oh
Date:	Wed, 19 Jan 2005 10:51:12 +0100

Mitch Harris wrote:

> Since these operators tell you about functions asymptotically (for
> larger and larger parameters, a better definition is:
>
> lim n->infinity g(n)/f(n) = 0

This does not define the same set of functions as
lim n->0 g(n)/f(n) = 0

which is the definition given in the stochastic process book I am using.
All I want to know is: are there two contradictory definitions for
little-oh, one seamingly used in maths and one used in computer science?

regards,
Andersen

From:	Mitch Harris
Subject:	Re: little-oh
Date:	Wed, 19 Jan 2005 11:42:36 +0100

Andersen wrote:
> Mitch Harris wrote:
>
>> Since these operators tell you about functions asymptotically (for
>> larger and larger parameters, a better definition is:
>>
>> lim n->infinity g(n)/f(n) = 0
>
> This does not define the same set of functions as
> lim n->0 g(n)/f(n) = 0
>
> which is the definition given in the stochastic process book I am using.

Then something weird is going on here. We want g(n) to be in o(f(n))
when g(n) is asymptotically "less than" f(n) (that is (like the first
definition you gave) beyond a certain point g(n) is strictly less
than f(n) for all n, and g(n) is negligeable in comparison to f(n).
This corresponds to n going to infinity, and g(n)/f(n) getting closer
and closer to 0, or

lim n->infinity g(n)/f(n) = 0

In you example it should be obvious that as n gets larger and larger,
the function g(n) = n is quite a bit smaller than f(n) = n^2. so you
want g(n) to be in the set o(f(n)). But

lim n->0 n/n^2 = lim n->0 1/n = infinity.

If your book gives the limit as going to 0, that is either a typo or
some bizarre mixup involving 0, infinity, etc.

> All I want to know is: are there two contradictory definitions for
> little-oh, one seamingly used in maths and one used in computer science?

Well, accounting for typos, I wouldn't say contradictory. The two
definitions work pretty much the same for most normal functions that
you come across in CS.

--
Mitch Harris
(remove q to reply)

From:	Lars Engebretsen
Subject:	Re: little-oh
Date:	Wed, 19 Jan 2005 17:58:41 +0100

Andersen writes:

> I have got lots of replies in this newsgroup and others. Most of them
> contradictory. Your answer is the only one which makes sense, so from
> the context you should infer which definition or limit that is
> implied. If it involves real numbers, such as
> "e^x = 1 + x/1! + x^2/2! + o(x^3)", it implies a definition where the
> limit goes to 0. If the context involves natural numbers, such as
> number of iterations in a loop, it is likely to imply a definition
> where the limit goes to infinity. Right?

Yes, that would be my interpretation as well.
(But you should have had big-Oh in the series expansion of e^x above.)

/Lars

From:	Andersen
Subject:	Re: little-oh
Date:	Wed, 19 Jan 2005 22:12:33 +0100

Lars Engebretsen wrote:

>
> Yes, that would be my interpretation as well.
> (But you should have had big-Oh in the series expansion of e^x above.)
>

I was wrong, I actually meant o(x) (I had read your sinus expansion
example). Would O(x^3) have really worked (or as in your sinus example
O(x^5) ), when x approaches 0 in all cases?

From:
Subject:	Re: little-oh
Date:	Wed, 19 Jan 2005 14:10:44 +0000 (UTC)

In article <356ep1F4j10a3U2@individual.net>,
Andersen writes:
>Hi,
>
>I am a computer science student. In computer science the little-oh
>function is defined as (unless I am wrong):
>if g(n) is in o(f(n)), then
> g(n) < n1 * f(n) for all n>=n2, for two constants n1 and n2 >= 0
>
>(reverse is true also)

None of the other responders have commented on this, but it seems to me that
this definition is not quite correct.

It should be g(n) is o(f(n)) if, for all n1 > 0, there exists n2 >= 0
such that g(n) < n1 * f(n) for all n>=n2. In other words, n1 and n2 are
not constants - n1 is an arbitrary positive number, and n2 depends on n1.

This is equivalent to lim n->infinity g(n)/f(n) = 0

>I recently bumped in to the following definition for little-oh notation
>in a math book (on stochastic processes) :
>if g(n) is in o(f(n)) then
>lim n->0 g(n)/f(n) = 0
>

I would say that in both mathematics and computer science, the default
usage of O, o and Theta notation refers to functions of x or n as x or n
approaches infinity, whether or not x is restricted to being an integer.

So this second definition is non-standard, and refers to behaviour as
n approaches 0. I find the use of n here misleading, because n is
more often than not used to denote an integer, whereas this definition
only makes sense in the context of n being a real (or maybe complex)
number.

Derek Holt.

From:	Lars Engebretsen
Subject:	Re: little-oh
Date:	Wed, 19 Jan 2005 15:53:39 +0100

mareg@mimosa.csv.warwick.ac.uk () writes:

> I would say that in both mathematics and computer science, the default
> usage of O, o and Theta notation refers to functions of x or n as x or n
> approaches infinity, whether or not x is restricted to being an integer.

What about the MacLaurin expansion? I.e., sin x = x + x^3/6 + O(x^5).
That was at least my first exposure to the big-Oh concept.

/Lars

From:	newstome at comcast.net
Subject:	Re: little-oh
Date:	Thu, 20 Jan 2005 15:59:57 -0600

mareg@mimosa.csv.warwick.ac.uk wrote:
> In article <356ep1F4j10a3U2@individual.net>,
> Andersen writes:
>>Hi,
>>
>>I am a computer science student. In computer science the little-oh
>>function is defined as (unless I am wrong):
>>if g(n) is in o(f(n)), then
>> g(n) < n1 * f(n) for all n>=n2, for two constants n1 and n2 >= 0
>>
>>(reverse is true also)
>
> None of the other responders have commented on this, but it seems to me that
> this definition is not quite correct.
>
> It should be g(n) is o(f(n)) if, for all n1 > 0, there exists n2 >= 0
> such that g(n) < n1 * f(n) for all n>=n2. In other words, n1 and n2 are
> not constants - n1 is an arbitrary positive number, and n2 depends on n1.

Yes, this was my comment too. It's a common mistake to take the
big-oh definition and change a <= into a < and say that makes
little-oh, but it doesn't (this is essentially what was done in the
definition above). In fact, changing the <= to < doesn't change
anything at all -- you still have the definition of big-oh. The "for
all" quantifier is really the important part of the little-oh definition.

--

That's News To Me!
newstome@comcast.net