[OT] stable algorithm with complexity O(n)

[Arnaud Delobelle]

Steven D'Aprano <steve at 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