Surely the halting problem only applies in the general case, i.e. given a ideal enough language you could use heuristics or give results applicable only when in xyz conditions e.g. when these nested for loops are in action it's O(n^2)
Yes, this is likely true - I really need to think about it more, though. I don't know how to do static or runtime analysis, so I can't say much about it