Hypothetical CS type question...

[gumpzilla]

[ QUOTE ]

*For the sake of the post, we can give 'meaningful' the definition of 'anything you can reasonably see someone wishing to program' So, obviously a very wide range of possible programs here. Basically, just dont make up a program for the sole purpose of discussing it in this thread.

[/ QUOTE ]

Tons of scientific computations can take a verrrry long time to compute. I could imagine many different types of quantum simulations, for example, that would blow up exponentially in time with addition of each new particle. In that sense, then, nearly all such programs will fall into the longest category. (EDIT: To be more explicit, let's say that the integer N characterizing the size of the problem has some threshold N0 where the problem ends up in category 3. ~100% of integers are bigger than N0, so to first order, all programs take longer.)

The one caveat is that the computer has finite space, so I can't just make these programs consider bigger and bigger problems without bound, otherwise 100% (in the measure theoretic sense) of the programs fall into the last category. But, in the real world, that's a concern. So I'd guess it's something like 95% of "interesting" programs as a lower bound fall into the last category.