I think this is again an easy one:
$DTIME(f(n)) \subset DSPACE(f(n))$
They say its trivial but I dont see it, why?
$DTIME(f(n^2)) \subset DSPACE(f(n^2))$
also be true? if yes why or why not?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
In each time step, the Turing machine can only move one position. Therefore, after $T$ time steps, the Turing machine can only have visited at most $T$ different positions, so its space usage (the number of cells it has visited or written to) must be at most $T$. Thus, the space complexity of any Turing machine is at most its time complexity.
If space is greater than time, as it must surf the space (in the related Turing machine), it will be contradicted by time is less than space. Hence, we can find that all problems which are in $DTIME(f(n))$ are in $DSPACE(f(n))$. and the proof is completed.
On the other hand, the size of input is important. Hence, if we set $m = n^2$ we reach to the first relation. Hence, it is true again.