Complexity — DTIME, DSPACE, complexity classes: Worked examples

Before any symbol appears, recall the three plain-word ideas we lean on everywhere:

Time $T (n)$ = the largest number of steps the machine takes over all inputs of length $n$ . ( $n = ∣ w ∣$ , the number of characters in the input.)
Space $S (n)$ = the largest number of distinct tape cells the machine ever writes to, over inputs of length $n$ .
A class like $P$ is just a bucket: the set of all problems whose $T (n)$ (or $S (n)$ ) fits under a stated ceiling.

Everything below is "measure the ceiling, then drop the problem in the smallest bucket that holds it."

The scenario matrix

Every complexity-classification question is one of these cells. Each worked example is tagged with the cell(s) it hits.

Cell	What makes it that case	Example
C1 — pure time bound	count steps, fit into $DTIME (n^{k})$	Ex 1
C2 — pure space bound	count cells, ignore steps, fit into $DSPACE$	Ex 2
C3 — "same problem, two buckets"	show a problem sits in a small AND a large class	Ex 3
C4 — nondeterministic guess	use a guess-and-check machine ( $N$ -classes)	Ex 4
C5 — degenerate / edge input	$n = 0$ , empty graph, single node — does the bound survive?	Ex 5
C6 — limiting / boundary of a bound	is $lo g n$ really enough? where does it break?	Ex 6
C7 — real-world word problem	translate English → resource count	Ex 7
C8 — exam twist (a trap)	a tempting-but-wrong classification	Ex 8

The rule used in every cell:

Example 1 — Counting characters (Cell C1: pure time)

Worked example Statement

$L = {w : w has more a ’s than b ’s}$ over the alphabet ${a, b}$ . Which time class?

Forecast: guess before reading on — is this linear, quadratic, or exponential in $n$ ?

Scan the tape once, keeping a running integer $d = (# a) - (# b)$ . Accept iff $d > 0$ at the end. Why this step? A single left-to-right pass touches each of the $n$ cells exactly once — that is the cheapest thing a machine can do that still "reads everything."
Count the steps, stating the machine model. We use a standard multi-tape TM: the input on a read-only tape, the counter $d$ written in binary on a separate work tape. Reading the input is $n$ head moves. For the counter cost, note that incrementing a $b$ -bit binary number touches only the low-order bits until a carry chain stops; the classic amortised argument (each bit position flips half as often as the one below it) gives total counter work $\leq 2 n$ over all $n$ increments — i.e. $O (1)$ amortised per increment on this model. Summing: $T (n) = O (n) + O (n) = O (n)$ . Why this step? Fitting into $DTIME (n^{k})$ only needs some polynomial $k$ ; here $k = 1$ already works, so the bound is as tight as possible. Naming the model (multi-tape, binary counter) is what licenses the " $O (1)$ amortised" claim — on a single-tape model it would be $O (lo g n)$ per step, still polynomial, so the class $P$ is unchanged either way.
Drop into the bucket. $O (n) = O (n^{1})$ , so $L \in DTIME (n) \subseteq P$ .

Verify: Take $w = aab$ , $n = 3$ . The single pass makes exactly $n = 3$ head moves, well inside the linear ceiling $O (n)$ . And $d = 2 - 1 = 1 > 0$ , so $aab$ is accepted, matching "more a's than b's." Amortised counter check: total bit-flips over $3$ increments $\leq 2 \cdot 3 = 6$ , i.e. $\leq 2 n$ . ✓

Example 2 — Same problem, but now count cells (Cell C2: pure space)

Worked example Statement

Same $L$ as Example 1. Which space class?

Forecast: the input is $n$ cells long — does deciding it need $n$ cells of work, or far fewer?

Separate input tape from work tape. Space is measured on the work tape only (the input is read-only). We only need to store the running difference $d$ . Why this step? The whole point of logspace is that you may read a long input while writing almost nothing.
How big can $d$ get, and why the " $+ 1$ "? The magnitude $∣ d ∣$ is at most $n$ , and a magnitude up to $n$ needs $⌈ lo g_{2} (n + 1)⌉$ bits (that is the general principle: writing a number of size $N$ in binary costs about $lo g_{2} N$ bits). But $d$ can be negative (more b's than a's), and binary alone only writes non-negative sizes — so we spend one extra bit to record the sign. Total $⌈ lo g_{2} (n + 1)⌉ + 1$ bits. Why this step? Making the sign bit explicit is the general rule for any signed counter: magnitude cost $lo g n$ , plus a constant $+ 1$ for direction — still $O (lo g n)$ .
Bucket. $S (n) = O (lo g n) \Rightarrow L \in DSPACE (lo g n) = L$ .

Verify: For $n = 1000$ , the counter needs at most $⌈ lo g_{2} 1001 ⌉ + 1 = 10 + 1 = 11$ bits — a fixed handful, growing like $lo g n$ , nowhere near $n = 1000$ . ✓

The picture below contrasts the two tapes: the input stretches across $n$ lavender cells (read-only), while the work tape holds only the tiny signed counter $d$ in a few mint cells. Look at the coral arrow — it points at the whole reason $L \in L$ : the work region never grows past $lo g n$ even as the input grows without bound.

Recall Why C1 and C2 give different classes for one problem

Time and space are different rulers. This one problem is $O (n)$ time and $O (lo g n)$ space. That is not a contradiction: Step 1 of the parent chain says time $\geq$ space, and indeed $n \geq lo g n$ . See Space vs Time Tradeoffs.

Example 3 — Palindromes in two buckets at once (Cell C3)

Worked example Statement

$PAL = {w : w = w^{reverse}}$ . Show it lands in both $P$ (a time bucket) and $L$ (a space bucket).

Forecast: which is the binding cost — the $n^{2}$ head-shuttling of the naive check, or the tiny counters?

Time view. Compare cell $i$ with cell $n - 1 - i$ for $i = 0, \dots, ⌊ n /2 ⌋$ . Each comparison drags the head across the string, $O (n)$ moves, and there are $n /2$ comparisons. Why this step? We want a step count, so we count the most expensive physical action (head travel).
$T (n) = \frac{n}{2} \cdot O (n) = O (n^{2}) \Rightarrow PAL \in DTIME (n^{2}) \subseteq P$ .
Space view. Store just two indices $i$ and $n - 1 - i$ . Each is a number $\leq n$ , i.e. $O (lo g n)$ bits. Re-read the input tape to fetch the characters at those positions. Why this step? We deliberately trade time for space: we re-scan the read-only input instead of copying it, so the work tape stays logarithmic.
$S (n) = O (lo g n) \Rightarrow PAL \in L$ .

Verify: $w = abba$ , $n = 4$ . Comparisons: $(0, 3)$ gives $a = a$ , $(1, 2)$ gives $b = b$ → accept. Number of comparisons $= n /2 = 2 \leq O (n^{2}) = 16$ . Indices peak at $n - 1 = 3$ , needing $⌈ lo g_{2} 4 ⌉ = 2$ bits. ✓

Example 4 — Reachability by guessing (Cell C4: nondeterminism)

Worked example Statement

$PATH = {⟨ G, s, t ⟩ : directed graph G has a path from s to t}$ . Show $PATH \in NL$ .

Forecast: a path can be $n - 1$ nodes long — surely storing it costs $O (n)$ space? Watch how nondeterminism dodges that.

Set up the guessing machine. Keep only two things on the work tape: cur (the node we are currently standing on, starts $= s$ ) and cnt (a step counter, starts $0$ ). Why this step? The trick of nondeterminism is that a nondeterministic machine may guess the next move and only needs enough memory to check one move at a time — never the whole path.
Loop: guess a neighbour nxt of cur; if the edge cur → nxt exists in $G$ , set cur := nxt, cnt := cnt + 1. If cur = t, accept.
Bound the counter. A simple path visits at most $n$ nodes, so if cnt exceeds $n$ without hitting $t$ , reject. Both cur and cnt are numbers $\leq n$ , i.e. $O (lo g n)$ bits each. Why this step? Capping cnt at $n$ prevents infinite wandering in a cycle, and keeps the counter logarithmic.
Bucket. $S (n) = O (lo g n)$ , machine is nondeterministic $\Rightarrow PATH \in NSPACE (lo g n) = NL$ .

Verify (via Savitch): deterministically the same problem costs $DSPACE ((lo g n)^{2})$ . Check the exponent arithmetic: Savitch squares the space bound, $(lo g n)^{2}$ , and $NL \subseteq DSPACE (lo g^{2} n)$ — consistent, since $lo g^{2} n$ is bigger than $lo g n$ but still tiny versus $n$ . ✓

The figure below draws a small graph. The two butter-coloured circles are $s$ (start) and $t$ (target); the coral arrows trace one guessed path $s \to a \to c \to t$ . The mint memory box at the bottom is the entire state the machine holds — just cur = c and cnt = 2. Notice it never records the visited path itself, which is exactly why the space stays $O (lo g n)$ .

Example 5 — Degenerate inputs: does the bound survive $n = 0$ and one-node graphs? (Cell C5)

Worked example Statement

Re-examine the machines above at their edge cases. (a) Example 1 on the empty string $ε$ . (b) Example 4 on a one-node graph, covering both $s = t$ and the (im)possibility of $s \neq = t$ .

Forecast: do edge cases break the classification, or just resolve trivially?

(a) Empty string, $n = 0$ . The scan makes $0$ moves; counter $d$ stays $0$ ; " $d > 0$ ?" is false, so $ε$ is rejected (it has $0$ a's, $0$ b's — correctly not more a's). Here $T (0) = 0$ , and $0$ trivially satisfies the bound $O (n)$ (any non-negative constant times $n$ is $\geq 0$ ). Why this step? Complexity ceilings are upper bounds; a machine that does less work on tiny inputs never violates them. Edge cases can only make you faster.
(b) One node, $s = t$ . The graph has a single node $v$ , and both endpoints must name a node of $G$ , so $s = t = v$ . The guessing machine sees cur = s = t immediately (cnt = 0) and accepts — a length-0 path exists (a node reaches itself). Space used: 2 tiny counters, $O (lo g 1) = O (1) \subseteq O (lo g n)$ . Why this step? The "reaches itself in $0$ steps" convention is exactly why we test cur = t before guessing.
(b) One node, $s \neq = t$ — why this input cannot occur. On a one-node graph there is only one node available, so a well-formed instance $⟨ G, s, t ⟩$ must set both $s$ and $t$ to that single node; " $s \neq = t$ " would name a node that does not exist in $G$ . A sensible machine treats such an ill-formed encoding as not in the language (reject in $O (1)$ ). So the case is not solved by silently switching to a bigger graph — it is classified as invalid input, still inside the $O (lo g n)$ ceiling. Why this step? Edge-case analysis must decide ill-formed inputs explicitly, rather than substituting a different, larger instance; leaving them undefined is exactly the gap the contract forbids.

Verify: All resolved cases produce the correct accept/reject and never exceed the stated ceilings ( $O (n)$ time, $O (lo g n)$ space). $lo g_{2} 1 = 0$ , so an $O (1)$ counter suffices — the bound is safe at the smallest input. ✓

Example 6 — The limiting boundary: when is $lo g n$ not enough? (Cell C6)

Worked example Statement

Consider $L_{copy} = {w w : w \in {0, 1}^{*}}$ (a string followed by an identical copy). Can we decide it in $L$ (logspace)? Where is the boundary?

Forecast: Example 3 did palindromes in logspace with two counters. Will the same two-counter trick work here?

Handle the length parity first. Let the total length be $m$ . Any member $w w$ has even length $m = 2 ∣ w ∣$ . So the very first check is: if $m$ is odd, reject immediately — no string of odd length can be a doubled string. This costs a single $O (lo g m)$ -bit length count and one parity test (look at the low bit of $m$ ), well inside logspace. Why this step? Covering the odd-length case up front means every remaining input is even, so the pairing in Step 2 is always well defined — no index ever runs off the tape.
Now the even case: try the logspace idea. With $m$ even, compare position $i$ with position $i + m /2$ for $i = 0, \dots, m /2 - 1$ , using two index counters, each $O (lo g m)$ bits. Why this step? This is the same two-pointer, re-read-the-input trick that put palindromes in $L$ — we test whether it transfers.
Check it works. Cell $i$ must equal cell $i + m /2$ . Two counters $\leq m$ ⇒ $O (lo g m)$ space. Together with the parity reject, $L_{copy}$ does land in $L$ . Why this step? We must actually verify the bound rather than assume the analogy — the counters here are genuinely logarithmic, and the odd-length branch is $O (1)$ extra work.
Where is the true boundary? The boundary of logspace is storing the string itself. If we had tried to copy $w$ onto the work tape to compare, that costs $∣ w ∣ = m /2$ cells $= O (m)$ space — that is $DSPACE (n)$ , far above $L$ . Why this step? The lesson of the limiting case: logspace forbids materialising the input; it only permits pointers into the read-only input. Cross that line and you leave $L$ .

Verify: Odd case: $m = 5$ (e.g. $10110$ ) is rejected instantly by parity ✓. Even case: $m = 6$ , $w = 101$ , string $101101$ . Compare $(0, 3) : 1 = 1$ , $(1, 4) : 0 = 0$ , $(2, 5) : 1 = 1$ → accept. Counters peak at $5$ , needing $⌈ lo g_{2} 6 ⌉ = 3$ bits ✓ (logspace). Copying instead would need $m /2 = 3$ cells — linear, confirming the boundary. ✓

Example 7 — Real-world word problem (Cell C7)

Before this example we need one symbol the parent note named but did not unpack: $NTIME$ .

Worked example Statement

A courier company has $c$ warehouses. It asks: "Is there a delivery route that visits every warehouse exactly once and returns to base, of total distance $\leq B$ ?" (the Travelling-Salesman decision problem, $TSP$ ). Classify it.

Forecast: the answer is famously not known to be in $P$ . In which bucket can we prove it sits?

Fix what "input length $n$ " means. The input is the $c \times c$ distance matrix plus the budget $B$ . Each entry and $B$ are numbers written in binary; let $β$ be the bit-length of the largest of them. Then the whole input has length $n = Θ (c^{2} β)$ — the $c^{2}$ matrix entries, each $β$ bits, plus $B$ . Why this step? Classification is measured against the actual encoded length $n$ , not the warehouse count $c$ . We must carry $β$ so that "polynomial in $n$ " is honest and includes the cost of the numbers themselves.
Guess a route (the nondeterministic step). A nondeterministic machine guesses an ordering (permutation) of the $c$ warehouses. Writing $c$ indices costs $O (c lo g c)$ bits, which is $\leq n$ — a polynomial-size certificate. Why this step? "Is there a route?" is an existence question — exactly what a single nondeterministic guess answers.
Verify the guess in polynomial time. Check the ordering is a genuine permutation (each warehouse appears exactly once — a linear scan) and sum the $c$ leg-distances; each addition handles $β$ -bit numbers in $O (β)$ time, so the total sum is $O (c β)$ , and the final compare to $B$ is $O (β)$ — all polynomial in $n$ . Why this step? $NP$ = "guess a certificate, then verify in time polynomial in the input length"; carrying $β$ shows the verifier is genuinely polynomial in $n$ , not just in $c$ .
Classify (NP), and give the deterministic bucket (EXP). Guess + poly verify $\Rightarrow TSP \in NTIME (n^{k}) \subseteq NP$ . Deterministically, enumerate all $(c - 1)!$ distinct tours (fix the base, permute the other $c - 1$ warehouses), verifying each in $O (c β)$ ⇒ $DTIME ((c - 1)! \cdot poly (n)) \subseteq EXP$ . Why this step? This is the whole point of Cell C7: translate an English business question into a resource count, then report the smallest provable bucket ( $NP$ ) alongside the deterministic upper bound ( $EXP$ ).

Verify: Tiny instance $c = 3$ , warehouses ${0, 1, 2}$ , symmetric distances $d (0, 1) = 1, d (1, 2) = 1, d (0, 2) = 1$ (so $β = 1$ bit each), budget $B = 3$ . A tour $0 \to 1 \to 2 \to 0$ has length $1 + 1 + 1 = 3 \leq 3$ → accept. Number of distinct tours to brute-force $= (c - 1)! = 2$ , matching the $EXP$ count. Input length estimate $c^{2} β = 9$ . ✓

Example 8 — The exam twist / trap (Cell C8)

Worked example Statement

True or false: "Because $TSP \in NP$ and we can also solve it deterministically in $EXP$ , it follows that $NP = EXP$ ." Diagnose the error and give the correct relationships.

Forecast: it sounds like a proof. Where exactly does it cheat? Guess the flaw before reading the steps.

Spot the leap. From "one problem lies in both $NP$ and $EXP$ " you may never conclude the classes are equal. Buckets can overlap without being identical. Why this step? A single language sitting in two classes only shows the classes intersect; class equality requires that every language of one class also lies in the other — a far stronger claim.
State what is actually proven. By the parent inclusion chain, $NP \subseteq PSPACE \subseteq EXP$ , so $NP \subseteq EXP$ . That inclusion is one-directional — it never claims the reverse. Why this step? We replace the false equality with the true, provable inclusion, so the reader keeps the correct fact.
Bring in the separation. The hierarchy theorems give $P ⊊ EXP$ — a strict separation, proved by diagonalisation (more time genuinely buys more languages). So the two ends of the chain are provably different; collapsing everything into one class contradicts a known theorem. Why this step? Showing a proven strict gap is the cleanest way to demonstrate the trap's conclusion is not merely unproven but outright false at the extremes.
Name the open part honestly. Whether $NP ⊊ EXP$ is strict, and whether $P = NP$ , are open problems. The trap sentence manufactures a "fact" where the field has none. Why this step? An exam answer earns marks by separating proven, false, and open — never by asserting convenient equalities.

Verify: Logical shape check — the pattern " $L \in A$ and $L \in B$ $\Rightarrow A = B$ " is invalid. Counterexample: the language ${ε}$ lies in $L$ and in $EXP$ , yet $L \neq = EXP$ (strict by the space hierarchy theorem). So the inference pattern is unsound, and the statement is false. ✓

Recall

Recall One problem, two rulers — what class was palindrome?

PAL is in both $P$ (time $O (n^{2})$ ) and $L$ (space $O (lo g n)$ ). ::: Time and space are independent ceilings.

Which cell needs a nondeterministic guess to stay in a small class?

Cell C4 —

PATH \in NL

by guessing the next node with only cur + cnt.

Why does copying the input onto the work tape kick you out of

L

It costs

O (n)

cells; logspace only allows

O (lo g n)

work cells (pointers into the read-only input, not copies).

Can "problem

L

is in

NP

and in

EXP

" prove

NP = EXP

No — overlap of one language never proves class equality;

P ⊊ EXP

is the only proven strict gap.