[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.
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
More information about the Python-list
mailing list