The halting problem is unsolvable in the general case, but there are lots of specific, practical cases where you can answer "yes, this program terminates". Is

The halting problem is unsolvable in the general case, but there are lots of specific, practical cases where you can answer "yes, this program terminates". Is it possible to specify the complexity of every arbitrary function? Probably not. Is it possible (and useful!) to specify the complexity of most functions you use on a daily basis? Absolutely. A stronger critique I heard once is that 'computer generated complexity analysis has too much noise in it', where you ask what is the complexity of this fn, and rather than giving you O(n^2), it gives you back O(n^2 * m * q * log(r) * s^4), but it turns out 's' is "always" a small number, and m & q are constants. You can improve (but not completely eliminate) this by doing empirical testing, i.e. "the statistical sample of 1000 test runs varying the input does appear to fit an O(n^2) curve".