stable algorithm with complexity O(n)

[Aaron Brady]

On Dec 14, 8:18 pm, Roy Smith <r... at panix.com> wrote:
> Steven D'Aprano <st... at REMOVE-THIS-cybersource.com.au> 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 definition.  The definition of triangle is, "a
> three-sided polygon".  Asking for a "four-sided triangle" is akin to asking
> for "a value of three which is equal to four".
>
> The second is only "impossible" because it contradicts our understanding
> (based on observation) of how the physical universe works.  Our
> understanding could simply be wrong.  We've certainly been wrong before,
> and we will undoubtedly be proven wrong again in the future.  When it comes
> to things like electromagnetic theory, it doesn't take too many steps to
> get us to the fuzzy edge of quantum physics where we know there are huge
> questions yet to be answered.

I agree.  Most of his examples were tautologies.  The magnet one was
the exception.

Then, to beat the O( n lg n ) limit, just break an assumption.

> > * or design a comparison sort which does fewer than O(n*log n) two-way
> > comparisons in the worst case, or fewer than O(n) comparisons in the best
> > case.

Make a three-way comparison, make a non-comparison sort, or make non-
random inputs.