[OT] stable algorithm with complexity O(n)
steve at REMOVE-THIS-cybersource.com.au
Sun Dec 14 04:16:19 CET 2008
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.
More information about the Python-list