Except verifying termination with a bound in the seconds of computation can be done in O(n), where n is the maximum number of seconds allowed (you can see that

Except verifying termination with a bound in the seconds of computation can be done in O(n), where n is the maximum number of seconds allowed (you can see that trivially by just waiting n seconds and killing the program if it doesn't terminate). On the other hand, if you try to limit a program's memory usage, it can take up to O(2^n) time to detect that a program with budget of n bits terminates (it might seem easier than that, but the program can go into an infinite loop without overflowing memory, like "while (1) {}"). You must consider that such a program can never have more than one state for each possible configuration of its allowed memory space (which is 2^n) and you can tell that it is in and infinite loop only when it repeats a previously used state. To do that correctly, then, takes a long time. Incidentally, this is why PSPACE (the class of decision problem decidable in a turing machine with polynomially limited space) seems a lot more powerful than P (the set of decision problems decidable using a polynomial amount of time).