Re: little-oh

From: David C. Ullrich (ullrich_at_math.okstate.edu)
Date: 01/20/05 

Date: Thu, 20 Jan 2005 05:24:43 -0600

I see it's already been said, but here's what I'd planned on
saying about all this:

> David C. Ullrich wrote:
>
>
>>
>> Quote the definitions from that book for us. Exactly, word-for-word
>> what the book says.
>>
>
> Do not have it here. It is the most classical text on algorithms, when I
> have access to it, I'll post the word-by-word citation of the text.

We need the word-for-word citation in order to determine
whether the book is simply wrong or you're misremembering
or misinterpreting what it says. For example:

> Meanwhile, this is off the top of my head:
[i]
> O(f(x)) = { g(x) | g(x) <= n1*f(x) for any x>=n2, where n1 and n2 are
> constants >= 0 }

[ii]
> o(f(x)) = { g(x) | g(x) < n1*f(x) for any x>=n2, where n1 and n2 are
> constants >= 0 }

Assuming that f(x) > 0 for all x, [i] and [ii] are precisely
equivalent. You're really claiming that this book says O and o
mean exactly the same thing?

This "where n1 and n2 are constants" could very well be what
you recall, when what it actually says is

[iii]
o(f(x)) = { g(x) | for every n1>0 there exists n2 so
that g(x) < n1*f(x) for any x>=n2 }.

The difference between [ii] and [iii] is the sort of thing
that a person might easily misremember off the top of his
head. I know that students in my classes always read things
loosely enough that they would think [ii] and [iii] were
the same. But [ii] and [iii] mean totally different things -
if what the book says is actually [iii] then the <=
versus < is irrelevant - [iii] does say precisely that
g/f -> 0.

> Functions f and g only have positive domains and codomains.
>
> Which implies o(f(x)) \subseteq O(f(x))
>
> In case of interest, Theta can then simply be defined as
> theta(f(x)) = { g(x) | ( g(x) \in O(f(x)) ) <===> ( f(x) \in O(g(x))) }
> a different independent definition commonly used is:
> theta(f(x)) = { g(x) | n1*f(x) <= g(x) <= n2*f(x), for any x>=n3, where
> n1, n2, n3 are constants >= 0 }
>
> Omega, and little omega are defined as lower bounds (similarly as O and
> o).
>
> I could be wrong, and I'll double check with Cormen and give you the
> text, but this is pretty much standard in any algorithms book in
> computer science. It is the other definitions which were knew to me. If
> interested, I got pretty exhaustive answers that made the differences
> lucid, same topic, in the newsgroup comp.theory.
>
> Regards,
> Andersen
>
>

************************

David C. Ullrich