If you have termination in general, it's much easier to get time bounds from input size. If you can't prove termination, you can't prove time bounds. And then

If you have termination in general, it's much easier to get time bounds from input size. If you can't prove termination, you can't prove time bounds. And then how do you improve on that, besides guesstimating and benchmarking?