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