[OT] stable algorithm with complexity O(n)

[Steven D'Aprano]

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.

All the positive thinking in the world won't help you:

* 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