On Mon, Dec 22, 2008 at 12:29 PM, wrote:
> On Dec 15, 10:00 pm, "cmdrrickhun...@yaho.com"
> wrote:
>> It can be proven that you cannot sort an arbitrarily large set of
>> numbers, given no extra information, faster than O(n log n).
>
> Cormen Leiserson and Rivest, "Algorithms", have a short clea
On Dec 15, 10:00 pm, "cmdrrickhun...@yaho.com"
wrote:
> It can be proven that you cannot sort an arbitrarily large set of
> numbers, given no extra information, faster than O(n log n).
Cormen Leiserson and Rivest, "Algorithms", have a short clear chapter
on
"Sorting in linear time":
" ... cou
Just because its such an interesting problem, I'll take a stab at it.
It can be proven that you cannot sort an arbitrarily large set of
numbers, given no extra information, faster than O(n log n). It is
provable using information theory. However, if your teacher is giving
you evil problems, ther
Dan Upton wrote:
And if n is small and sparse (ie, k > n) , O(k*n) for radix sort could
be worse than O(n^2). You could also ask why people make such a big
deal about quicksort over mergesort, since mergesort has a guaranteed
O(n log n) time whereas quicksort can be O(n^2) on pathological cases
On Mon, Dec 15, 2008 at 11:05 AM, wrote:
>> Non-comparison sorts are a useful technique, but it's changing the
>> problem, and they are only useful in very limited circumstances. There's
>> a good reason that most sort routines are based on O(n*log n) comparison
>> sorts instead of O(n) bucket so
On Dec 15, 11:05 am, prueba...@latinmail.com wrote:
> > Non-comparison sorts are a useful technique, but it's changing the
> > problem, and they are only useful in very limited circumstances. There's
> > a good reason that most sort routines are based on O(n*log n) comparison
> > sorts instead of O
> Non-comparison sorts are a useful technique, but it's changing the
> problem, and they are only useful in very limited circumstances. There's
> a good reason that most sort routines are based on O(n*log n) comparison
> sorts instead of O(n) bucket sorts or radix sorts.
>
This is an assumption tha
On Sun, 14 Dec 2008 21:12:13 -0800, Aaron Brady wrote:
> On Dec 14, 8:18 pm, Roy Smith wrote:
>> Steven D'Aprano wrote:
>> > All the positive thinking in the world won't help you:
>>
>> > * make a four-sided triangle;
>>
>> > * split a magnet into two individual poles;
>>
>> These two are fundam
On Mon, Dec 15, 2008 at 2:12 PM, Aaron Brady wrote:
>
> I agree. Most of his examples were tautologies. The magnet one was
> the exception.
A proof is nothing more than a tautology :) The fact that pi is not
rational is not trivial (but certainly has been proved for some time
now).
cheers,
D
On Dec 14, 8:18 pm, Roy Smith wrote:
> Steven D'Aprano wrote:
> > All the positive thinking in the world won't help you:
>
> > * make a four-sided triangle;
>
> > * split a magnet into two individual poles;
>
> These two are fundamentally different problems.
>
> The first is impossible by definit
On Dec 14, 6:04 pm, greg wrote:
> Lie Ryan wrote:
> > "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?
>
> There's a big difference between an unsolvable problem and an
> unsolve
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. lea
Aaron Brady wrote:
>So, what's the group policy on helping with homework? rhetorical>
In my book anyone who is dumb enough to ask for homework help on a
newsgroup and doesn't acknowledge that when they hand in their answer
deserves whatever they get. Oh, and of course there are 2 deliberate
2008/12/13 Aaron Brady
> On Dec 13, 1:17 pm, Duncan Booth wrote:
> > "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
On Dec 13, 1:17 pm, Duncan Booth wrote:
> "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 h
15 matches
Mail list logo
