Alex Martelli wrote: > Michael Hoffman <[EMAIL PROTECTED]> wrote: > >> Alex Martelli wrote: >>> Arnaud Delobelle <[EMAIL PROTECTED]> wrote: >>> ... >>>>>>> decorated.sort() >>> ... >>>>> def index(sequence): >>>>> return sorted(range(len(sequence)), key=sequence.__getitem__) >>> ... >>>> But really these two versions of rank are slower than the original one >>>> (as sorting a list is O(nlogn) whereas filling a table with >>>> precomputed values is O(n) ). >>> Wrong, because the original one also had a sort step, of course, so it >>> was also, inevitably, O(N log N) -- I've quoted the .sort step above. >> Well, counting the index() function that is called in both cases, the >> original rank() had one sort, but my version has two sorts. > > That doesn't affet the big-O behavior -- O(N log N) holds whether you > have one sort, or three, or twentyseven.
I've taught programming classes before, and I would have had to fail anybody who misunderstood speed badly enough to claim that something repeating an O(N log N) algorithm 27 times was no faster than doing it once. ;-) As Arnaud points out, asymptotic behavior is not the same as speed. His original statement that the more recently proposed definitions of rank() are slower than the OP's may be correct. And if it's not, it's not because they're all O(N log N). -- Michael Hoffman -- http://mail.python.org/mailman/listinfo/python-list
