On Sat, 13 Dec 2008 19:17:41 +0000, Duncan Booth wrote: > I think you must have fallen asleep during CS101. The lower bound for > sorting where you make a two way branch at each step is O(n * log_2 n), > but if you can choose between k possible orderings in a single > comparison you can get O(n * log_k n).
I think you might have been sleeping through Maths 101 :-) The difference between log_2 N and log_k N is a constant factor (log_2 k) and so doesn't effect the big-oh complexity. -- Steven -- http://mail.python.org/mailman/listinfo/python-list
