[OT] stable algorithm with complexity O(n)

[Steven D'Aprano]

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