Steven D'Aprano <st...@remove-this-cybersource.com.au> writes: > 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.
It affects it if k is a function of n. In this particular example, we can set k=n so we get O(n). -- Arnaud -- http://mail.python.org/mailman/listinfo/python-list
