0
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by David Richerby complexity-theory Jul 3 at 10:22

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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.

$\endgroup$
  • $\begingroup$ So space is in average cases less than time? Why is EXPSPACE bigger than EXPTIME then? $\endgroup$ – WeCanBeFriends Jul 3 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 at 1:28

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