Mathematics.

computational complexity

Space Complexity

Theory of Computation45 minDifficulty6 out of 10

You should know: complexity classes

Overview

Space complexity measures how much memory (tape/working storage) an algorithm needs as a function of input size, complementing time complexity's focus on running time. Classifying problems by space usage yields classes like PSPACE (polynomial space), L (logarithmic space, using only a read-only input plus O(log n) working memory), and NL (nondeterministic logarithmic space) — and reveals surprising relationships between space and time, most famously Savitch's theorem, which shows nondeterministic and deterministic space usage are far more closely related to each other than nondeterministic and deterministic TIME are believed to be.

Intuition

Time complexity asks 'how many steps?'; space complexity asks 'how much scratch paper?' A problem might take a very long time but need only a tiny notepad (e.g. checking every possible password one at a time, remembering just the current guess), while another problem might finish quickly but need to remember an enormous amount of intermediate data. Crucially, since a machine can't use more distinct memory configurations than time steps without repeating itself (and looping forever, if it's supposed to halt), space complexity classes tend to be more tightly nested and better understood than their time counterparts — space is, in a real sense, a 'cheaper' and more reusable resource than time, since the same memory cells can be overwritten and reused across many steps.

Formal Definition

Definition

Space complexity is measured by the number of tape cells a Turing machine uses on its work tape(s) (the read-only input tape doesn't count, allowing sublinear space classes):

SPACE(f(n))={ L:L is decided by a TM using O(f(n)) work-tape cells on inputs of length n }\text{SPACE}(f(n)) = \{\, L : L \text{ is decided by a TM using } O(f(n)) \text{ work-tape cells on inputs of length } n \,\}
Deterministic space class
PSPACE=⋃kSPACE(nk)\text{PSPACE} = \bigcup_{k} \text{SPACE}(n^k)
PSPACE — polynomial space
L=SPACE(log⁡n),NL=NSPACE(log⁡n)L = \text{SPACE}(\log n), \qquad NL = \text{NSPACE}(\log n)
Logarithmic space classes
NSPACE(f(n))⊆SPACE(f(n)2)\text{NSPACE}(f(n)) \subseteq \text{SPACE}(f(n)^2)
Savitch's theorem

Notation

NotationMeaning
LLProblems decidable using only O(log n) work-tape space
NLNLProblems decidable nondeterministically using O(log n) space
PSPACE\text{PSPACE}Problems decidable using polynomial work-tape space (any amount of time)

Theorems

Theorem 1: Savitch's theorem
For f(n)≥log⁡n, NSPACE(f(n))⊆SPACE(f(n)2). In particular, PSPACE=NPSPACE.\text{For } f(n) \ge \log n, \ \text{NSPACE}(f(n)) \subseteq \text{SPACE}(f(n)^2). \text{ In particular, PSPACE} = \text{NPSPACE}.
Theorem 2: Space hierarchy relative to time
P⊆PSPACE,L⊆NL⊆P,and PSPACE⊆EXPTIME (space can never exceed time, up to a constant factor per cell visited).\text{P} \subseteq \text{PSPACE}, \quad L \subseteq NL \subseteq P, \quad \text{and PSPACE} \subseteq \text{EXPTIME (space can never exceed time, up to a constant factor per cell visited).}
Theorem 3: Space hierarchy theorem
If f(n) is space-constructible and g(n)=o(f(n)), then SPACE(g(n))⊊SPACE(f(n)) — strictly more space strictly increases what’s decidable.\text{If } f(n) \text{ is space-constructible and } g(n) = o(f(n)), \text{ then SPACE}(g(n)) \subsetneq \text{SPACE}(f(n)) \text{ — strictly more space strictly increases what's decidable.}

Applications

Embedded systems and mobile devices with severely limited RAM care about space complexity independently of time — an algorithm using O(log n) working memory (class L) can process huge inputs on tiny hardware even if it isn't the fastest option.

Worked Examples

  1. A nondeterministic algorithm just needs to guess the next vertex in a path from s to t one step at a time, storing only the CURRENT vertex (and a step counter up to n), never the whole path.

    store current vertex v, counter i≤n  ⟹  O(log⁡n) bits\text{store current vertex } v, \ \text{counter } i \le n \implies O(\log n) \text{ bits}

  2. Since a vertex label and a counter up to n each need only O(log n) bits to write down, total space is O(log n), regardless of how long the actual path turns out to be.

    PATH∈NL\text{PATH} \in NL

Answer: PATH is in NL because a nondeterministic machine can verify reachability by guessing one vertex at a time, remembering only the current vertex and a bounded step count — both O(log n) bits — never the full path.

Practice Problems

Difficulty 6/10

Explain intuitively why space complexity classes tend to nest more tightly (be better understood) than the analogous time complexity classes.

Difficulty 6/10

An embedded sensor device has only a few kilobytes of RAM but can afford to run an algorithm for several seconds. Which complexity measure should the engineers prioritize when choosing an algorithm, and why?

Difficulty 6/10

Savitch's theorem states that:

Common Mistakes

Common Mistake

Assuming space complexity and time complexity always tell the same story about an algorithm's efficiency.

An algorithm can be fast but memory-hungry, or slow but extremely memory-frugal (e.g. some O(log n)-space algorithms revisit information repeatedly, trading time for space) — the two measures are related (space ≤ time, roughly) but far from interchangeable.

Common Mistake

Believing PSPACE = NPSPACE is an open problem like P vs NP.

PSPACE = NPSPACE is a PROVEN theorem (a direct corollary of Savitch's theorem), unlike P vs NP, which remains famously open — space behaves very differently from time in this respect.

Quiz

Space complexity measures:
Savitch's theorem shows that removing nondeterminism from a space-bounded computation costs:
The class L consists of problems decidable using:

Historical Background

Space complexity as a formal field grew out of the same early-1960s-1970s wave of complexity theory that produced time complexity classes. Walter Savitch's 1970 paper proved Savitch's theorem, showing any nondeterministic Turing machine using space f(n) can be simulated deterministically in space O(f(n)²) — a dramatically tighter relationship than the exponential blowup believed necessary to simulate nondeterministic TIME deterministically. This resolved (relative to space) a question analogous to P vs NP, and the resulting classes PSPACE, NPSPACE, L, and NL became core objects of study.

  1. 1965

    Hartmanis and Stearns formalize time and space complexity classes and prove foundational hierarchy theorems

    Juris Hartmanis, Richard Stearns

  2. 1970

    Walter Savitch proves Savitch's theorem: NSPACE(f(n)) ⊆ DSPACE(f(n)²)

    Walter Savitch

  3. 1970s

    PSPACE-completeness is developed, with problems like quantified Boolean formula (QBF) shown PSPACE-complete

Summary

  • Space complexity measures memory usage (work-tape cells) as a function of input size, distinct from time complexity.
  • Key classes: L (log space), NL (nondeterministic log space), PSPACE (polynomial space).
  • Savitch's theorem: NSPACE(f(n)) ⊆ SPACE(f(n)²) — a much tighter deterministic/nondeterministic relationship than for time, giving PSPACE = NPSPACE.
  • Space is a 'cheaper', more reusable resource than time, since memory cells can be repeatedly overwritten — this is why space complexity classes are better understood/more tightly nested than time classes.

References

  1. WebsiteWikipedia — DSPACE
  2. WebsiteWikipedia — Savitch's theorem