Re: [OT] stable algorithm with complexity O(n)

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

"Diez B. Roggisch" <deets@xxxxxxxxxxxxx> 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

.

Relevant Pages

  • Re: On the complexity of determining whether n numbers are distinct
    ... this can be shown by reducing the problem to one of sorting but the ... bounds for algebraic computation trees" by Michael Ben-Or proves the n ... log n lower bound in the algebraic decision tree model of computation. ...
    (comp.theory)
  • Re: Sorting by complex alphanumeric data
    ... Access uses 30 as the lower bound for rwo digit ... I didn't know that you could write statements into the sorting and grouping ... most likely could use in the Report Sorting & Grouping what I gave you above ...
    (microsoft.public.access.reports)
  • Re: [OT] stable algorithm with complexity O(n)
    ... I have to create stable algorithm for sorting n numbers from interval ... To beat n * log_2 n just use a bucket sort: ... maximum you can sort them digit by digit for O, ...
    (comp.lang.python)
  • Re: [OT] stable algorithm with complexity O(n)
    ... Unless I grossly miss out on something in computer science 101, the lower bound for sorting is O. ... The lower bound for sorting where you make a two way branch at each step is O, but if you can choose between k possible orderings in a single comparison you can get O. ... 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, 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 ==1 so you get O ...
    (comp.lang.python)
  • Re: stable algorithm with complexity O(n)
    ... lower bound for sorting is O. ... To beat n * log_2 n just use a bucket sort: ... The generic sort theorems also assume you can compare arbitrarily ...
    (comp.lang.python)