Even if a problem is computationally solvable "in theory," it may not be solvable "in practice" if the solution requires
an excessive amount of time (or memory space, etc.).
Let \(M\) be a deterministic Turing machine that halts on all inputs. The time complexity(running time) of \(M\) is
the function \(f: \mathbb{N} \to \mathbb{N}\), where \(f(n)\) is the maximum number of steps that \(M\) uses on any input
of length \(n\). We say that \(M\) runs in time \(f(n)\).
Usually we are interested in the running time of the algorithm for large inputs, and onsider only the highest order
term of the expression for the running time. This is called asymptotic analysis.
Big-O notation:
Let \(f\) and \(g\) be functions \(f, g: \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\). The highest order term is \(3n^3\). So,
we can say \(f(n) = O(n^3)\) with \(c = 11\), and \(n_0 = 1\).
(Check: \(f(n) \leq 3n^3 + 2n^3 + n^3 + 5n^3\))
Little-o notation:
Let \(f\) and \(g\) be functions \(f, g: \mathbb{N} \to \mathbb{R}^+\). Say that
\[
f(n) = o (g(n))
\]
if
\[
\lim_{n \to \infty} \frac{|f(n)|}{|g(n)|} = 0.
\]
Equivalently, for any real number \(c >0\), a number \(n_0\) exists where
\[
\forall n \geq n_0, \, f(n) < c \, g(n).
\]
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
Let \(t: \mathbb{N} \to \mathbb{R}^+\) be a function. Define the time complexity class,
\(\text{ TIME}(t(n))\), to be the collection of all languages that are decidable by an \(O(t(n))\) time Turing machine.
Consider the Turing machine algoithm, \(M_1\) for the language:
\[
A = \{0^k 1^k | 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 if both 0s and 1s remain on the tape.
Scan across the tape, crossing off a single 0 and a single 1.
If 0s(1s) still remain after all the 1s(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})")
The running time is
\[
O(n) + \frac{n}{2}O(n) + O(n) = O(n^2).
\]
Then we can say that \(A \in \text{ TIME}(n^2)\). This class contains all languages that can be decided in
\(O(n^2)\) time.
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 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.
\(M_2\) has time complexity \(O(n) + (1 + \log n )O(n) + O(n) = O(n \log n)\). Moreover, if we introduce another tape,
time complexity becomes \(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 hit the first 1. At the same time, copy the 0s onto Tape-2
Scan across the 1s on Tape-1 until the the end of the string. cross off a 0 on Tape-2 when read a 1 on Tape-1. If
all 0s are crossed off before all the 1s are read, reject.
If all the 0s are crossed off, accept. If any 0s remain, reject.
The following code demonstrate actual runnning times of \(M_2\) and the two-tape Turing machine, \(M_3\).
#from js import performance
import time
# Accept all strings generated from the language A = {0^k 1^k | k >= 0} with O(n log 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(n):
print("n = ", n)
return "0" * n + "1" * n
if __name__ == "__main__":
# Define the length of the string.
input_str = worst_case_input(1000000)
# Measure machine 2: (O(n log n))
start = time.time()
machine2(input_str)
end = time.time()
print("Machine2 (O(n log 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, but in complexity theory,
the choice of model affects the time complexity of languages. In practice, it is hard to say that \(M_1\) and \(M_3\)
are the "same." In the code, we set \(n = 1,000,000\), which is too large for \(M_1\) that has time complexity \(O(n^2)\).
Note: Even though \(M_3\) has a theoretically better time complexity (O(n)), some practical factors can result in slower
execution on a webpage compared to \(M_2\) in the environment. (Run the code in your local environment. You will get better result.)
Also, depending on the implementation , practical runtimes can be worse than what theoretical complexities suggest.
High-level languages such as Python often widen the gap between theoretical complexity and practical runtime.
Often Python code runs slower than compiled languages like C.
Class \(P\)
In fact, at most a square difference between the time complexity of problems measured on deterministic
single-tape Turing Machines and multitape Turing machines.
Formally, let \(t(n)\) be a function, where \(t(n) \geq n\). Then every \(t(n)\) time multitape Turing machine
has an eqivalent \(O(t^2(n))\) time sigle-tape Turing machine.
In practical programming, it is important to consider the polynomial differences between algorithms in
terms of running time. For example, the difference 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, \(2^{1000}\) quickly exceeds astronomical numbers, so exponential time
models represents a fundamentally harder computational challenge. Below, we define an important class of languages in
complexity theory:
Class \(P\):
\(P\) is the class of languages that are decidable in polynomial time on a deterministic single-tape Turing
machine:
\[
P = \bigcup_k \text{ TIME}(n^k).
\]
When a proble is in \(P\), there is a method of solving it that runs in time \(n^k\) for some constant \(k\).
Note: In practice, the size of \(k\) does matter.
We could say that P is mostly, corresponds to the class of problems that are realistically solvable on a modern computer.
We will revisit this topic after discussing graph theory more.