On Thu, May 18, 2006 at 03:31:26PM -0400, Jacques Carette wrote:

> In Computer Algebra, people use Groebner bases all the time.  They have 
> doubly-exponential worst-case complexity -- but seem to work rather well 
> in practice.  So I have stopped paying attention to worst-case; average 
> case, when available, does matter a lot more.

Except when someone made a decision like this, in say a revision control
system, and suddenly you discover that you've provoked a worst case
scenario, and it suddenly takes hundreds of cpu hours to check in a file
rather than a few seconds.

For something like a compiler, worse case behavior is very important.  It
is not generally acceptable for a build to just hang in the compiler.

Dave