space complexity
When we ask how hard a problem is, time is the obvious meter: how many steps? But there is a second, just as honest meter: how much scratch paper does the computation need? Picture a clerk solving a puzzle at a desk. They can think for hours (lots of time) yet only ever keep a single index card of notes (little space), or scribble across a whole wall (lots of space). Space complexity measures that second resource. It counts the amount of working memory a machine uses, as a function of the size n of the input.
We measure it on a Turing machine: the space used on an input is the number of distinct tape cells the read/write head ever visits before halting. If a machine never writes outside the first c times log n cells on any input of length n, we say it runs in O(log n) space; if it stays within a polynomial number of cells, polynomial space; and so on. Just as with time, we focus on worst-case growth: the most cells used over all inputs of each size. The space bound s(n) is a function, and we sort machines into classes by how fast s(n) grows.
Space behaves strikingly differently from time, and that is what makes this field exciting. The same cell can be erased and reused over and over, so a machine can take a huge number of steps yet revisit only a few cells. Reusability gives space surprising powers (nondeterminism barely helps, complements come for free) that time is not known to share. Honest caveat: every cell used costs at least one step to write, so space used is never more than time used, but the reverse can fail wildly. Counting space, not steps, opens a whole second view of what is easy and what is hard.
To check whether a string of n bits is a palindrome, a clever machine keeps only two pointers, one at each end, plus a tiny counter: that is O(log n) space (a pointer into n cells needs about log n bits), even though it makes about n comparisons (linear time). Memory used can be far smaller than time used.
Space counts cells visited; the palindrome check uses many steps but only logarithmic memory.
Space used never exceeds time used (you cannot visit a cell without a step), but a machine can use vastly more time than space by reusing the same cells.