(None)

"Perry E. Metzger" <perry@imsi.com> writes:

> algorithm that factors numbers or even just breaks RSA in O(log(n))
> time or less (where n is the length of the number being factored or
> the public key). I'd offer more, but it would be cruel. If you don't
> know what the notation O(f(n)) means, please don't come back asking.
     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.


                                          --Jeff
--
======  ======    +----------------jgostin@eternal.pha.pa.us----------------+
  ==    ==        | The new, improved, environmentally safe, bigger, better,|
  ==    ==  -=    | faster, hypo-allergenic, AND politically correct .sig.  |
====    ======    | Now with a new fresh lemon scent!                       |
PGP Key Available +---------------------------------------------------------+

Jeff Gostin says:
> "Perry E. Metzger" <perry@imsi.com> writes:
> 
> > algorithm that factors numbers or even just breaks RSA in O(log(n))
> > time or less (where n is the length of the number being factored or
> > the public key). I'd offer more, but it would be cruel. If you don't
> > know what the notation O(f(n)) means, please don't come back asking.
>      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.

O(x) isn't a function invocation, its a complexity theory notation --
it basically means "order of". For instance, it can be proven that a
generalized sort algorithm that relies only on compares can be written
with time complexity no greater than a constant factor plus a constant
factor times n log n, where n is the number of elements. The constants
don't really matter, so we just call it an O(n log(n)) algorithm.

This topic can get really rich and I haven't explained it terribly
well -- I suggest a book on theoretical computer science. Knuth may
have a good explanation, but I don't recall.

Perry

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