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

Steven D'Aprano steve at REMOVE-THIS-cybersource.com.au
Mon Dec 15 02:48:43 CET 2008

```On Sun, 14 Dec 2008 21:42:33 +0000, Lie Ryan wrote:

> 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

Because as you described it, it *hasn't* happened before. There is the
world of difference between an unsolvABLE problem and one that is
unsolvED.

* make a four-sided triangle;

* write down a completely accurate rational expansion for pi or the
square-root of 2;

* split a magnet into two individual poles;

* find an integer solution to 3*n = 7;

* solve the Halting Problem;

* fit n items into n-1 pigeonholes without putting two items in the one
pigeonhole;

* create a compression algorithm that will compress random data;

* 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.

Some things really don't have a solution, no matter how much power of
positive thinking you apply to it.

--
Steven

```