[OT] stable algorithm with complexity O(n)

[Lie Ryan]

On Sat, 13 Dec 2008 19:17:41 +0000, Duncan Booth wrote:

> "Diez B. Roggisch" <deets at nospam.web.de> wrote:
> 
>> David Hláčik schrieb:
>>> Hi guys,
>>> 
>>> i am really sorry for making offtopic, hope you will not kill me, but
>>> this is for me life important problem which needs to be solved within
>>> next 12 hours..
>>> 
>>> I have to create stable algorithm for sorting n numbers from interval
>>> [1,n^2] with time complexity O(n) .
>>> 
>>> Can someone please give me a hint. Would be very very thankful!
>> 
>> Unless I grossly miss out on something in computer science 101, the
>> lower bound for sorting is O(n * log_2 n). Which makes your task
>> impossible, unless there is something to be assumed about the
>> distribution of numbers in your sequence.
>> 
>> Who has given you that assignment - a professor? Or some friend who's
>> playing tricks on you?
>> 
> 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).
> 
> To beat n * log_2 n just use a bucket sort: for numbers with a known
> maximum you can sort them digit by digit for O(n log_k n), and if you
> don't restrict yourself to decimal then k can be as large as you want,
> so for the problem in question I think you can set k=n and (log_n n)==1
> so you get O(n)
> 

I'm sure someday, there will be a student who comes to class late and 
sees this on the board: "Design a comparison sorting algorithm that has 
better than O(n * log n) lower bound complexity." The unsuspecting 
student copied it, thinking it's a homework. He crunched to the problem, 
going to various meditations and yoga classes before finding a way that 
works just before deadline, handing out the work a bit late. Six weeks 
later, his professor called and said: "You know what you just did? You've 
just found a problem that was supposed to be an example of unsolvable 
problem."

It has happened before, why not again? 
http://www.snopes.com/college/homework/unsolvable.asp