Time and Space Complexity of a TM

Theory of Computation & Computer Graphics — Turing Machine, NEC licence examination syllabus (Nepal Engineering Council).

Time and Space Complexity of a Turing Machine

How do you even MEASURE how "expensive" a TM's computation is?

⏱️ Measuring Cost

Time complexityThe number of steps (tape-head moves) the TM takes, as a function of input length n — expressed using Big-O, same notation from your data structures subject.

Space complexityThe number of distinct tape cells the TM actually uses during its computation, as a function of n.

💡 One-liner: "Why do we measure TM complexity as a function of input LENGTH rather than input VALUE?" → Complexity theory cares about how resource use scales as inputs grow, and length is the natural, consistent measure across different types of input.

The relationship between the two

Time and space are not independent, and one direction of the relationship is immediate.

A Turing machine can only use a tape cell by moving its head there, and each move is one step. So a machine running for t steps can visit at most t cells: space ≤ time, always. The converse fails badly — a machine can use very little tape and still run for an enormous number of steps, or loop forever, so small space says nothing about time.

💡 That asymmetry is worth stating in an exam answer, because it explains why space-bounded classes can contain problems with large time requirements. Bounding the tape does not bound the number of configurations the machine passes through.

Why the model barely matters

A reasonable objection: a two-tape machine solves some problems faster than a one-tape machine, so which one is the complexity measured on?

The answer is that it makes no difference to the classification. Simulating a multi-tape machine on a single-tape one costs at most a polynomial slowdown — typically squaring the running time. So a problem solvable in polynomial time on one model is solvable in polynomial time on the other.

This is why complexity theory draws its main line at polynomial versus exponential rather than at any finer distinction. That boundary is the one that survives changing the machine model, and a definition that shifted depending on how many tapes you chose would not be describing the problem at all.

Worst case, unless stated otherwise

Complexity is quoted for the worst case input of each length by default. Average-case analysis exists but requires assuming a distribution over inputs, and different assumptions give different answers — so unless a question says otherwise, it is asking for the worst case.

Syllabus points

Measuring time & space complexity

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.