While we're talking about annoyances

[Alex Martelli]

Michael Hoffman <cam.ac.uk at mh391.invalid> wrote:
   ...
> >> 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 for me, I would fail somebody who thought they could compare speed
this way -- if the O(N log N) executed 27 times took (on a given
machine) 1 millisecond times N times log N, and the other one (on the
same machine) 1 second times N times log N (and in the big-O notation
you can NEVER infer what the multiplicative constant is), for example,
such a comparison would be totally of base.

> 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).

And if it is, it's not because of the "one sort" versus "two sorts": by
that sole criterion you just cannot guess (sensibly) at speed (measuring
is much better, though it has its own pitfalls).


Alex