0
$\begingroup$

I believe I have heard that you can never have more space than the algorithms running time. I could be wrong, maybe other way around. What is the intuition behind this?

| cite | improve this question | | | | |
$\endgroup$
0
$\begingroup$

A Turing machine moves the tape by one space per time unit. Worst case, if all moves were in the same direction, the space used would be exactly the same as the time used.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ So space is in average cases less than time? Why is EXPSPACE bigger than EXPTIME then? $\endgroup$ – WeCanBeFriends Jul 3 '19 at 0:32
  • $\begingroup$ Sorry, I don’t know. I haven’t studied complexity theory. I looked those up, and I can see why everything in EXPTIME must be in EXPSPACE, but I don’t see why there may be problems in EXPSPACE that aren’t in EXPTIME. Perhaps you should post this as another question. $\endgroup$ – Tom Zych Jul 3 '19 at 1:28

Not the answer you're looking for? Browse other questions tagged or ask your own question.