David Brown 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.
>  
>
I see you've used ClearCase!   Rather unpleasant experience.

>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.
>
Not the compiler, the super-optimizing pass in the compiler.  I 
completely agree that the base compiler should not hang a build, and 
that complexity (including worst-case) there matters a lot.

Speaking of which, have you ever tried to compile an Ocaml program with 
a LOT of functors in it?  It requires quite a bit of patience...

Jacques