## [ITOC-ch8] SPACE COMPLEXITY

**Space somplexity**

- M is
**deterministic** - f(n) is the maximum number of
*tape cells*that M*scans*on any**input of length**n.

**nondeterministic Space complexity**

- M is
**nondeterministic** - f(n) is the maximum number of
*tape cells*that M*scans*on any**branch**on any**input of length**n.