Velocity Reviews > [OT] stable algorithm with complexity O(n)

# [OT] stable algorithm with complexity O(n)

David Hláčik
Guest
Posts: n/a

 12-13-2008
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!

D.

Diez B. Roggisch
Guest
Posts: n/a

 12-13-2008
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?

Diez

David Hláčik
Guest
Posts: n/a

 12-13-2008
> 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

There is n numbers from interval [1 , n^2]
I should do measurement for :
n = 500, 1000, 1500, 2000, ..., 4500, 5000

O(n) means linear complexivity, so complexivity of algorithmus must be
linear, which i have to prove.

>
> Who has given you that assignment - a professor? Or some friend who's
> playing tricks on you?

It is official assignment , by professor from Data Structures &
Algorithms course.

>
> Diez
> --
> http://mail.python.org/mailman/listinfo/python-list
>

MRAB
Guest
Posts: n/a

 12-13-2008
Diez B. Roggisch 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'm assuming that the numbers are integers. I can think of an O(n)
algorithm for this particular problem provided that n isn't huge, but if
it's your assignment then it's up to you to discover it.

Diez B. Roggisch
Guest
Posts: n/a

 12-13-2008
Duncan Booth schrieb:
> "Diez B. Roggisch" <(E-Mail Removed)> 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)

Thanks. I *totally* forgot about that.

Diez

Guest
Posts: n/a

 12-13-2008
On Dec 13, 1:17*pm, Duncan Booth <(E-Mail Removed)> wrote:
> "Diez B. Roggisch" <(E-Mail Removed)> 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)

Minor detail: with k= n, you have log_n (n^2)= 2, so you get O(2n)= O

The generic sort theorems also assume you can compare arbitrarily
large numbers in constant time, which isn't true. That is, for any
given machine, there exist numbers that you can't compare on them in
constant time. But with a known upper bound k, you can just use a k-
bit machine.

<rhetorical>So, what's the group policy on helping with homework? </
rhetorical>

Arnaud Delobelle
Guest
Posts: n/a

 12-13-2008
"David HlĂĄÄik" <(E-Mail Removed)> writes:

> 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!
>
> D.

I don't have an algorithm but I have an implementation

def sort2(numbers):
"sort n positive integers in O(n) provided that they are all < n^2"
N = len(numbers)
units = [[] for i in xrange(N)]
tens = [[] for i in xrange(N)]
for n in numbers:
units[n % N].append(n)
for l in units:
for n in l:
tens[n / N].append(n)
return [n for l in tens for n in l]

--
Arnaud

Steven D'Aprano
Guest
Posts: n/a

 12-14-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.

--
Steven

Lev Elbert
Guest
Posts: n/a

 12-14-2008
1. Comparison sorts have n*ln(n) complexity - does not do
2. Counting sort has the complexity O(d), where d is domain (in our
case n^2) - does not do.
3. Radix sorts have the complexity O(n*k), where k is number of bits
in integer. (32?) There are 2 variants:
a. most significant digit (MSD),
b. least significant digit (LSD).

The LSD radix sort is stable.

Good luck.

Arnaud Delobelle
Guest
Posts: n/a

 12-14-2008
Steven D'Aprano <(E-Mail Removed)> 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