Even if a problem is computationally solvable in principle, it may be unsolvable in practice if the solution requires an
excessive amount of time or memory. Complexity theory studies these quantitative distinctions.
Definition: Time Complexity (Running Time)
Let \(M\) be a deterministic Turing machine that halts on all inputs. The time complexity
(or running time) of \(M\) is the function \(f\colon \mathbb{N} \to \mathbb{N}\), where
\(f(n)\) is the maximum number of steps that \(M\) uses on any input of length \(n\).
Usually we are interested in the running time of an algorithm on large inputs. We then consider only the highest-order
term of the expression for the running time, disregarding both its coefficient and any lower-order terms. This is
called asymptotic analysis.
Convention.
Throughout this page, \(\mathbb{R}^+\) denotes the set of nonnegative real numbers,
\(\mathbb{R}^+ = \{x \in \mathbb{R} : x \geq 0\}\).
Definition: Big-O notation
Let \(f\) and \(g\) be functions \(f, g\colon \mathbb{N} \to \mathbb{R}^+\). Say that
\[
f(n) = O (g(n))
\]
if positive integers \(c\) and \(n_0\) exist such that for every integer \(n \geq n_0\),
\[
f(n) \leq c \, g(n).
\]
We say that \(g(n)\) is an asymptotic upper bound for \(f(n)\).
For example, consider \(f(n) = 3n^3 + 2n^2 + n + 5\). Its highest-order term is \(3n^3\), and \(f(n) = O(n^3)\) with \(c = 11\)
and \(n_0 = 1\). (Indeed, \(f(n) \leq 3n^3 + 2n^3 + n^3 + 5n^3 = 11n^3\) for every \(n \geq 1\).)
Definition: Little-o notation
Let \(f\) and \(g\) be functions \(f, g\colon \mathbb{N} \to \mathbb{R}^+\) with \(g(n) \gt 0\) for all
sufficiently large \(n\). Say that
\[
f(n) = o (g(n))
\]
if
\[
\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0.
\]
In other words, for any real number \(c \gt 0\), a number \(n_0\) exists such that
\[
f(n) \lt c \, g(n) \quad \text{for all } n \geq n_0.
\]
Little-o notation is used when we want to express that one function grows strictly slower than another, whereas big-O
notation merely provides a (not necessarily tight) upper bound.
Time Complexity Classes
Definition: Time Complexity Class
Let \(t\colon \mathbb{N} \to \mathbb{R}^+\) be a function. The time complexity class \(\operatorname{TIME}(t(n))\)
is the collection of all languages that are decidable by an \(O(t(n))\)-time deterministic single-tape Turing machine.
To illustrate how the time bound we can establish for a language depends on the algorithm, consider the language
\[
A = \{0^k 1^k \mid k \geq 0\}.
\]
We define \(M_1\) as follows:
On input string \(w\):
Scan across the tape and reject if a 0 is found to the right of a 1.
Repeat the following if both 0s and 1s remain on the tape:
Scan across the tape, crossing off a single 0 and a single 1.
If 0s still remain after all the 1s have been crossed off, or if 1s still remain after all the 0s have been crossed off, reject. Otherwise, if neither 0s nor 1s remain on the tape, accept.
The sample code for \(M_1\) is as follows:
# Accept all strings generated from the language A = {0^k 1^k | k >= 0}
def machine1(w):
tape = list(w)
# Scan the tape and reject if a 0 is found to the right of a 1. : O(n)
seen_one = False
for c in tape:
if c == '1':
seen_one = True
elif c == '0' and seen_one: # a 0 appears after a 1.
return False
# Repeatedly cross off one 0 and one 1 as long as both are present. : O(n^2)
while '0' in tape and '1' in tape:
# Find the first uncrossed 0 and mark it.
idx0 = tape.index('0')
tape[idx0] = 'X'
# Find the first uncrossed 1 and mark it.
idx1 = tape.index('1')
tape[idx1] = 'X'
# If there are any uncrossed 0s or 1s remaining, reject the input. : O(n)
if '0' in tape or '1' in tape:
return False
# Otherwise, accept the input.
return True
if __name__ == "__main__":
# Test cases
test_cases = [
("", True), ("0011", True), ("0", False), ("0101", False), ("001", False), ("011", False),
("1100", False), ("0000011111", True), ("01", True), ("1111", False)
]
for inp, expected in test_cases:
result = machine1(inp)
print(f"({inp!r}) = {result} (expected: {expected})")
Let us analyze the running time of \(M_1\) on an input of length \(n\). Step 1 scans the entire tape once, in \(O(n)\) time.
Step 2 is a loop. Each pass through its body (Step 2a) removes one 0 and one 1, so the loop runs at most \(n/2\) times, and
every pass scans the tape to locate the next uncrossed symbols at a cost of \(O(n)\). Step 3 performs one final scan, again in
\(O(n)\) time. The total running time is therefore
\[
\underbrace{O(n)}_{\text{Step 1}} + \underbrace{\tfrac{n}{2} \cdot O(n)}_{\text{Step 2}} + \underbrace{O(n)}_{\text{Step 3}} = O(n^2).
\]
It follows that \(A \in \operatorname{TIME}(n^2)\). This class contains all languages that can be decided in \(O(n^2)\) time on a
deterministic single-tape Turing machine.
We can improve \(M_1\). We define \(M_2\) as follows:
On input string \(w\):
Scan across the tape and reject if a 0 is found to the right of a 1.
Repeat the following if some 0s and some 1s remain on the tape:
Scan across the tape, checking whether the total number of 0s and 1s remaining is even or odd. If it is odd, reject.
Scan again across the tape, crossing off every other 0 starting with the first 0, and then crossing off every other 1 starting with the first 1.
If no 0s and no 1s remain on the tape, accept. Otherwise, reject.
For \(M_2\), Step 1 again costs \(O(n)\). Step 2 is a loop whose body (Steps 2a and 2b) halves the count of remaining symbols at
each iteration by crossing off every other one starting from the first. The loop therefore terminates after at most
\(\log_2 n + 1\) iterations, and each iteration performs full scans of the tape in \(O(n)\). Step 3 is a final \(O(n)\) sweep.
The total is
\[
\underbrace{O(n)}_{\text{Step 1}} + \underbrace{(\log_2 n + 1) \cdot O(n)}_{\text{Step 2}} + \underbrace{O(n)}_{\text{Step 3}} = O(n \log n).
\]
Hence \(A \in \operatorname{TIME}(n \log n)\). Moreover, if we introduce a second tape, the time complexity drops to \(O(n)\),
linear time. We define \(M_3\) as follows:
On input string \(w\):
Scan across Tape-1 and reject if a 0 is found to the right of a 1.
Scan across the 0s on Tape-1 until hitting the first 1. At the same time, copy the 0s onto Tape-2.
Scan across the 1s on Tape-1 until the end of the string. Cross off a 0 on Tape-2 for each 1 read on Tape-1. If
all 0s are crossed off before all the 1s are read, reject.
If all the 0s have been crossed off, accept. If any 0s remain, reject.
On a two-tape machine, each step of \(M_3\) sweeps each tape at most a constant number of times, with no nested loops over the
input. Step 1 costs \(O(n)\). Step 2 copies the 0s in \(O(n)\), and Step 3 reads the 1s and decrements Tape-2 in \(O(n)\).
Step 4 is \(O(1)\). The total is
\[
O(n) + O(n) + O(n) + O(1) = O(n).
\]
Hence \(M_3\) decides \(A\) in \(O(n)\) time on a two-tape Turing machine. The following code implements \(M_2\) and the
two-tape Turing machine \(M_3\)
on Python lists and times them. Because list slicing never rescans discarded symbols, this implementation of \(M_2\) runs in
\(O(n)\) time rather than the \(O(n \log n)\) of the tape machine.
#from js import performance
import time
# Accept all strings generated from the language A = {0^k 1^k | k >= 0}, following M2 (this list version runs in O(n))
def machine2(w):
tape = list(w)
# Reject if a 0 is found to the right of a 1.
seen_one = False
for ch in tape:
if ch == '1':
seen_one = True
elif ch == '0' and seen_one:
print("Invalid order: found a 0 after a 1.")
return False
# Build lists of indices for uncrossed 0s and 1s.
zero_indices = [i for i, ch in enumerate(w) if ch == '0']
one_indices = [i for i, ch in enumerate(w) if ch == '1']
# Repeat as long as both 0s and 1s remain.
while zero_indices and one_indices:
# Check whether the total remaining is even.
total_remaining = len(zero_indices) + len(one_indices)
if total_remaining % 2 != 0:
return False
# Cross off every other 0 starting with the first 0.
zero_indices = zero_indices[1::2] # This "removes" every other 0.
# Cross off every other 1 starting with the first 1.
one_indices = one_indices[1::2]
# Accept if both lists are empty.
if zero_indices or one_indices:
return False
return True
# Two-tape Turing machine: O(n)
def machine3(w):
tape1 = list(w)
tape2 = [None] * len(w) # Pre-allocated tape2 for 0s only
tape2_index = 0 # Points to the current "end" of tape2
# Ensure all 0s precede 1s, copy 0s to tape2.
i = 0
while i < len(tape1):
if tape1[i] == '0':
tape2[tape2_index] = '0'
tape2_index += 1
elif tape1[i] == '1':
break
else:
return False # Invalid character
i += 1
# Match each 1 with a 0 from tape2.
while i < len(tape1):
if tape1[i] == '1':
if tape2_index == 0:
return False # No 0 to match
tape2_index -= 1 # "Pop" from tape2 (backward)
elif tape1[i] == '0':
return False # Found a 0 after 1 - invalid order
else:
return False # Invalid character
i += 1
return tape2_index == 0 # All 0s matched
# In this case, accepted strings often cause the worst-case performance
# because they force the algorithm to do full verification.
def worst_case_input(k):
print("k = ", k, ", n = ", 2 * k)
return "0" * k + "1" * k
if __name__ == "__main__":
# Define the length of the string.
input_str = worst_case_input(1000000)
# Measure machine 2 (list version: O(n))
start = time.time()
machine2(input_str)
end = time.time()
print("Machine2 (list version, O(n)) took:", end - start, "seconds")
# Measure machine 3: (O(n))
start = time.time()
machine3(input_str)
end = time.time()
print("Machine3 (O(n)) took:", end - start, "seconds")
In computability theory, \(M_1\), \(M_2\), and \(M_3\) are all equivalent, since they decide the same language \(A\). In
complexity theory, they differ. The machines \(M_1\) and \(M_2\) run on the same single-tape model with different algorithms,
while \(M_3\) uses a second tape, and both choices affect the running time. In practice, it is hard to say that \(M_1\) and
\(M_3\) are the "same." In the code, the input is \(0^k 1^k\) with \(k = 1{,}000{,}000\), so its length is
\(n = 2{,}000{,}000\), which would be expensive for \(M_1\), whose time complexity is \(O(n^2)\).
Because both implementations run in linear time, the measured gap reflects constant factors and the execution environment rather
than the gap between \(O(n \log n)\) and \(O(n)\), and in the browser the order of the two can even reverse. More generally,
practical runtimes depend on the implementation and can be worse than theoretical complexity suggests. High-level languages such
as Python widen this gap, and Python code typically runs slower than equivalent code in a compiled language such as C.
Class \(P\)
How much does the choice of machine model affect time complexity? It turns out that the difference between a single-tape and a
multitape Turing machine is at most a polynomial (specifically, quadratic) slowdown. A running time of \(t(n)\) on a multitape
machine becomes \(O(t^2(n))\) on a single tape.
Theorem: Single-Tape vs. Multitape Simulation
Let \(t(n)\) be a function with \(t(n) \geq n\).
Every \(t(n)\)-time multitape Turing machine
has an equivalent \(O(t^2(n))\)-time single-tape Turing machine.
Proof sketch.
We show that the construction from
the multitape-single-tape equivalence
can be carried out within \(O(t^2(n))\) time. Recall that the simulating single-tape machine \(T\) stores the contents
of the multitape machine \(M\)'s \(k\) tapes consecutively on a single tape, separated by a delimiter \(\#\), with the head
positions marked by dotted symbols.
Bounding the active portion.
Since \(M\) runs for at most \(t(n)\) steps, each of its heads visits at most \(t(n) + 1\) cells, and the input occupies
\(n \leq t(n)\) cells of the first tape. Each virtual tape therefore has length at most \(t(n) + 1\). Summing over the \(k\)
tapes and adding the \(k + 1\) delimiters, the active portion of \(T\)'s tape (from the leftmost to the \((k+1)\)-st
delimiter) has length at most \(k(t(n) + 1) + k + 1 = O(t(n))\), since \(k\) is a fixed constant of the machine.
Cost per simulated step.
To simulate one step of \(M\), \(T\) makes two passes over its active portion: the first to read the symbols under all \(k\)
virtual heads, and the second to update the virtual tape contents and head positions according to \(M\)'s transition
function. Each pass costs \(O(t(n))\). The machine \(T\) may also need to shift a portion of its tape rightward by one cell,
up to \(k\) times, to make room when a virtual head moves into a previously unused cell. Each such shift also costs
\(O(t(n))\). The total cost of simulating one \(M\)-step is therefore \(O(t(n))\).
Total time.
The initial reformatting of the input takes \(O(n)\) steps. Simulating the at most \(t(n)\) steps of \(M\) costs at most
\(t(n) \cdot O(t(n)) = O(t^2(n))\). The total running time of \(T\) is
\[
O(n) + O(t^2(n)) = O(t^2(n)),
\]
where the simplification uses the assumption \(t(n) \geq n\).
In practical programming, it is important to consider the polynomial differences between algorithms in terms of
running time. The gap between \(O(n)\) and \(O(n^3)\) becomes critical as \(n\) grows larger. For instance, if \(n = 1{,}000\),
then \(n^3 = 1{,}000{,}000{,}000\).
However, in complexity theory, we regard these polynomial differences as less significant. Indeed, we say that reasonable
deterministic computational models are polynomially equivalent. In contrast, at the same \(n = 1{,}000\), a
running time of \(2^n\) is already \(2^{1000} \gt 10^{300}\) steps, so exponential-time algorithms represent a
fundamentally harder computational challenge. Below, we define an important class of languages in complexity theory:
Definition: Class \(P\)
\(P\) is the class of languages that are decidable in polynomial time on a deterministic
single-tape Turing machine:
\[
P = \bigcup_k \operatorname{TIME}(n^k).
\]
A language is in \(P\) if and only if there exists an algorithm that decides it in time
\(O(n^k)\) for some fixed constant \(k\).
The class \(P\) roughly corresponds to the class of problems that are realistically solvable on a modern computer. In practice,
the degree \(k\) and the constant factors also matter. An \(O(n^{100})\) algorithm is technically polynomial but practically
infeasible. The distinction between polynomial and exponential time is the central theme of complexity theory.
The page on Class NP introduces nondeterministic
computation, which leads to one of the deepest open questions in mathematics and computer science: does \(P = NP\)?