zlacker

>>makira+(OP)
I think it is very intuitive that more space beats the pants off of more time.

In time O(n) you can use O(n) cells on a tape, but there are O(2^n) possible configurations of symbols on a tape of length n (for an alphabet with 2 symbols), so you can do so much more with n space than with n time.

>>LPisGo+Y9
But you also spend time on updating cells, so it is not that intuitive.

>>qbane+1c
I’m not sure what you mean here. If you’re in the realm of “more space” than you’re not thinking of the time it takes.

More precisely, I think it is intuitive that the class of problems that can be solved in any time given O(n) space is far larger than the class of problems that can be solved in any space given O(n) time.

>>LPisGo+Ac
If your program runs in O(n) time, it cannot use more than O(n) memory (upper bound on memory usage.

If your program uses O(n) memory, it must run at least in O(n) time (lower bound on time).

>>Almond+Af
In other words M <= T.