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. Alex -- http://mail.python.org/mailman/listinfo/python-list
