On Sat, 13 Dec 2008 19:17:41 +0000, Duncan Booth wrote: > "Diez B. Roggisch" <de...@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 -- http://mail.python.org/mailman/listinfo/python-list