Michael Hoffman <[EMAIL PROTECTED]> 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 -- http://mail.python.org/mailman/listinfo/python-list
