While we're talking about annoyances

[Alex Martelli]

Michael Hoffman <cam.ac.uk at mh391.invalid> wrote:

> Alex Martelli wrote:
> > Arnaud Delobelle <arnodel at googlemail.com> 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