While we're talking about annoyances

[Michael Hoffman]

Alex Martelli wrote:
> 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.

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