Re: little-oh

From: Andersen (alibandali_at_hotmail.com)
Date: 01/19/05 

Date: Thu, 20 Jan 2005 00:33:06 +0100

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.

Meanwhile, this is off the top of my head:

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

o(f(x)) = { g(x) | g(x) < n1*f(x) for any x>=n2, where n1 and n2 are
constants >= 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

Relevant Pages

  • Re: Cauchy-Riemann equations
    ... In article, David C. Ullrich ... |>has both partial derivatives on Omega, ...
    (sci.math)
  • Re: little-oh
    ... > David C. Ullrich wrote: ... It is the most classical text on algorithms, ... multiple of f, but that it also is eventually less than *any* nonzero ...
    (sci.math)
  • Re: concentration / compactness
    ... Take C to be the uniformly continuous functions on Omega and C* its dual. ... David C. Ullrich ...
    (sci.math)
  • Re: Sigma algebra problem
    ... How can one show that B is a set of such omegas in Omega ... If possible, give pointers, not spoilers. ... David C. Ullrich ...
    (sci.math)
  • Re: concentration / compactness
    ... and take u_m>=1 in Omega. ... Dirac Mass at 0. ... David C. Ullrich ...
    (sci.math)