At 7:39 PM 11/25/1996, The Deviant wrote:

...

Rigorous proofs of the non-existence of an algorithm are not new. Neither are rigorous proofs that any algorithm which can solve a given problem requires a minimal running time. Or, in an even stronger sense,

Hrmmm... I seem to see a problem (namely Moore's first law) in assigning anything a "minimal running time". Perhaps "minimal instruction count" would be more suited to your example. Because if you're talking about time, it essentially boils down to "the longer something takes the less time it takes".

"Introduction to Algorithms" by Cormen, Leiserson, and Rivest is a good introduction to Big O notation. The problem you raise is the motivation behind this notation. diGriz