From: "Perry E. Metzger" <perry@imsi.com>
Date: Fri, 17 Jun 94 14:02:27 PDT
To: jgostin@eternal.pha.pa.us
Subject: Re: (None)
In-Reply-To: <940617160624Y4Wjgostin@eternal.pha.pa.us>
Message-ID: <9406172102.AA02980@snark.imsi.com>
MIME-Version: 1.0
Content-Type: text/plain



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