Re: (None)

["Perry E. Metzger" <perry@imsi.com>]

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