Classification of Algorithms

An algorithm that produces the right answer is not, by itself, good enough. If it would take a billion years to finish, it is useless in practice no matter how correct it is. Algorithmic complexity is the study of how the resources an algorithm needs — chiefly time — grow as its input grows, and the resulting classification of algorithms is one of the most practically important ideas in the whole course. It draws a series of lines: between problems that are computable and those that are not; among computable problems, between those that are tractable (efficiently solvable) and those that are intractable (solvable only at impractical cost); and, at the heart of it all, the famous classes P, NP and NP-complete, whose relationship is the most celebrated open question in computer science. Mastering this classification tells you which problems to attack head-on, and which demand a cleverer, more pragmatic response.

---

Spec Mapping

This lesson addresses the Theory of Computation strand of the AQA A-Level Computer Science specification (7517), in the area concerned with classifying algorithms by complexity (around section 4.4.4, building on the algorithmic-efficiency work of section 4.3). You are expected to understand orders of complexity expressed in Big-O notation — from $O(1)$O(1) through logarithmic, linear, $O(n \log n)$O(nlogn), polynomial, exponential and factorial $O(n!)$O(n!); to distinguish polynomial from exponential growth and hence tractable from intractable problems; to understand, at A-Level depth, the complexity classes P, NP and NP-complete, the meaning of "verifiable in polynomial time", and the open question of whether P = NP; and to explain why this classification matters for real problem solving. The treatment below is descriptive rather than a verbatim quotation of the specification.

---

Orders of Complexity

Big-O notation captures the dominant growth rate of an algorithm's running time as the input size $n$n becomes large, ignoring constant factors and lower-order terms (because for large $n$n those are swamped by the leading term). The standard orders, from best to worst, are:

Order	Name	Behaviour as $n$n grows	Typical example
$O(1)$O(1)	Constant	Unaffected by input size	Array index lookup; pushing onto a stack
$O(\log n)$O(logn)	Logarithmic	Grows very slowly; doubling $n$n adds a constant	Binary search on a sorted array
$O(n)$O(n)	Linear	Doubling $n$n doubles the work	Linear search; one pass over a list
$O(n \log n)$O(nlogn)	Linearithmic	Slightly worse than linear	Merge sort; quicksort (average case)
$O(n^2)$O(n2)	Quadratic	Doubling $n$n quadruples the work	Bubble sort; comparing all pairs
$O(n^3)$O(n3)	Cubic	Doubling $n$n multiplies work by 8	Naive matrix multiplication
$O(2^n)$O(2n)	Exponential	Adding one to $n$n doubles the work	Trying every subset; naive Boolean satisfiability
$O(n!)$O(n!)	Factorial	Grows faster than any exponential	Trying every permutation; brute-force Travelling Salesman

The orders $O(1)$O(1) to $O(n^k)$O(nk) (any fixed power $k$k) are the polynomial orders; $O(2^n)$O(2n) and $O(n!)$O(n!) are the super-polynomial orders. That single dividing line — polynomial versus super-polynomial — is the most consequential boundary in the entire lesson, for reasons the next table makes brutally clear.

---

Polynomial versus Exponential Growth: a Worked Comparison

It is one thing to state that exponential growth is worse; it is far more persuasive to see the numbers. The table below shows the approximate number of basic operations each order requires for a handful of input sizes.

Order	$n = 5$n=5	$n = 10$n=10	$n = 20$n=20	$n = 50$n=50	$n = 100$n=100
$O(\log n)$O(logn)	~2	~3	~4	~6	~7
$O(n)$O(n)	5	10	20	50	100
$O(n \log n)$O(nlogn)	~12	~33	~86	~282	~664
$O(n^2)$O(n2)	25	100	400	2,500	10,000
$O(n^3)$O(n3)	125	1,000	8,000	125,000	1,000,000
$O(2^n)$O(2n)	32	1,024	~1.05 × 10⁶	~1.13 × 10¹⁵	~1.27 × 10³⁰
$O(n!)$O(n!)	120	~3.6 × 10⁶	~2.4 × 10¹⁸	~3 × 10⁶⁴	~9.3 × 10¹⁵⁷

Read across the bottom two rows and the point lands with force. At $n = 50$n=50 a cubic algorithm needs a mere 125,000 operations — trivial for a modern processor doing billions of operations a second. But an $O(2^n)$O(2n) algorithm at $n = 50$n=50 already needs about $10^{15}$1015 operations (days of computation), and the factorial row at $n = 50$n=50 reaches $\sim 3 \times 10^{64}$∼3×1064 — vastly more operations than there are atoms in the Earth. The decisive contrast is in how the orders respond to a bigger input: making $n$n ten times larger multiplies the work of an $O(n^3)$O(n3) algorithm by a fixed factor of $1{,}000$1,000, but adding just ten to the input of an $O(2^n)$O(2n) algorithm multiplies its work by roughly $1{,}000$1,000 as well — exponential growth punishes every single increment. This is exactly why the polynomial / exponential boundary is taken as the dividing line between feasible and infeasible.

To make the practical impact concrete, suppose each operation takes one nanosecond ($10^{-9}$10−9 s):

Order	Time at $n = 50$n=50
$O(n^3)$O(n3)	125,000 ns ≈ 0.000125 s (instant)
$O(2^n)$O(2n)	~$1.13 \times 10^{15}$1.13×1015 ns ≈ 13 days
$O(n!)$O(n!)	~$3 \times 10^{64}$3×1064 ns ≈ longer than the age of the universe many times over

No realistic improvement in hardware rescues an exponential algorithm: even a computer a million times faster only lets you increase $n$n by about 20 for an $O(2^n)$O(2n) algorithm before you are back to the same wall. Speed multiplies what you can do by a constant; exponential growth devours constants. This is the lesson's central practical truth.

---

Tractable and Intractable

Armed with the polynomial/exponential boundary, we can classify computable problems by the efficiency of the best known algorithm for them.

Class	Definition	Examples
Computable	A problem solvable by some algorithm — a Turing machine that halts on all inputs	Sorting, searching, shortest path
Non-computable	A problem no algorithm can solve for all inputs	The halting problem
Tractable	A computable problem that has a polynomial-time algorithm — $O(n^k)$O(nk) for some constant $k$k	Sorting ($O(n \log n)$O(nlogn)), shortest path (Dijkstra, polynomial), primality testing
Intractable	A computable problem with no known polynomial-time algorithm — the best known solutions are exponential or worse	Travelling Salesman (optimal route, $O(n!)$O(n!) brute force), Boolean satisfiability, optimal timetabling

Two points of precision matter enormously here, and examiners test both:

1. Tractable means "polynomial-time algorithm exists"; intractable means "no polynomial-time algorithm is known". The word "known" is doing real work. For most famous intractable problems it has not been proved that no polynomial algorithm exists — only that nobody has ever found one despite decades of effort. (Whether one could exist is exactly the P = NP question below.)
2. Intractable is not the same as non-computable. An intractable problem is computable — an algorithm exists and will, given enough time, deliver the correct answer. The obstacle is time, not possibility. A non-computable problem like the halting problem has no algorithm at all, regardless of time. Conflating "too slow" with "impossible" is one of the most penalised errors in this topic.

---

Complexity Classes: P and NP

To make the tractable/intractable idea rigorous, theoretical computer science focuses on decision problems — problems with a yes/no answer — and defines two central classes.

Class P (Polynomial time)

P is the set of decision problems that can be solved by an algorithm running in polynomial time. Informally, P is the class of efficiently solvable yes/no problems.

Examples: Is this list sorted? Is this number prime? Is there a path of length at most $k$k between these two nodes? Each can be answered by a known polynomial-time algorithm.

Class NP (Non-deterministic Polynomial time)

NP is the set of decision problems for which a proposed solution can be verified in polynomial time — even if finding that solution might take far longer. The name comes from "non-deterministic polynomial": a non-deterministic machine could "guess" a solution and then check it in polynomial time.

The classic illustration is the Travelling Salesman decision problem: is there a route visiting all $n$n cities with total distance at most $k$k? If someone hands you a candidate route, you can verify it easily — add up the distances and compare to $k$k, an $O(n)$O(n) check. But finding such a route in the first place may require examining astronomically many possibilities. Verifying is easy; finding seems hard — that gap is the essence of NP.

The relationship and the great open question

• Every problem in P is also in NP. If you can solve a problem quickly, you can certainly verify a proposed solution quickly (just solve it yourself and compare). So $P \subseteq NP$P⊆NP.
• The open question — does $P = NP$P=NP? Is every problem whose solutions can be verified quickly also solvable quickly? Nobody knows. It is the most famous unsolved problem in computer science, one of the Clay Mathematics Institute's Millennium Prize Problems (worth a million US dollars). The overwhelming expert expectation is that $P \neq NP$P=NP — that some problems really are fundamentally harder to solve than to check — but no proof exists either way.

flowchart TB
    NP["NP — verifiable in polynomial time"]
    NP --> NPC["NP-complete — the hardest problems in NP"]
    NP --> P["P — solvable in polynomial time"]
    P -. "Is P = NP?\n(unknown)" .- NPC

(The diagram shows the believed picture: P sits strictly inside NP, with the NP-complete problems at NP's hard frontier. If P = NP turned out to be true, all three regions would collapse into one.)

---

NP-Complete and NP-Hard

Within NP, some problems are the hardest possible, and they are tied together in a remarkable way.

NP-complete

A decision problem is NP-complete if it satisfies both conditions:

1. It is in NP — a proposed solution can be verified in polynomial time.
2. Every other problem in NP can be reduced to it in polynomial time — i.e. any NP problem can be efficiently transformed into an instance of this one.

NP-complete problems are therefore the "hardest" problems in NP, and they share a startling fate: if even one NP-complete problem were found to have a polynomial-time algorithm, then every problem in NP would, and P would equal NP. They stand or fall together. Conversely, if $P \neq NP$P=NP (as most believe), then no NP-complete problem has a polynomial-time solution. This is why finding an efficient algorithm for any NP-complete problem would be one of the greatest results in the history of the subject.

Famous NP-complete problems include:

• Boolean satisfiability (SAT) — the first problem proved NP-complete (the Cook–Levin theorem);
• the Travelling Salesman decision problem;
• graph colouring (can a graph be coloured with $k$k colours so no two adjacent nodes share a colour?);
• the knapsack problem;
• subset sum (is there a subset of these numbers summing to exactly $t$t?).

The practical significance is that recognising a problem as NP-complete is a signal to stop searching for an efficient exact algorithm and to reach instead for the pragmatic responses described below — because an efficient exact method almost certainly does not exist.

NP-hard

A problem is NP-hard if every NP problem reduces to it in polynomial time, but it is not required to be in NP itself (so its solutions might not even be verifiable in polynomial time — it may not be a decision problem at all). Every NP-complete problem is NP-hard and in NP; an NP-hard problem is "at least as hard as the hardest problems in NP" but possibly harder still. The optimisation version of the Travelling Salesman problem ("find the shortest route", not merely "is there one under $k$k?") is NP-hard.

---

Decision Problems versus Optimisation Problems

The classes P, NP and NP-complete are defined for decision (yes/no) problems, but the real-world questions we care about are often optimisation problems. The two are closely related.

Type	Question	Example
Decision	"Does a solution meeting this bound exist?" (yes/no)	"Is there a route visiting all cities with total distance $\leq k$≤k?"
Optimisation	"What is the best solution?"	"What is the shortest route visiting all cities?"

An optimisation problem is at least as hard as its decision version: if you could find the optimal route, you could certainly answer "is there one under $k$k?" by comparing the optimum to $k$k. This is why, although the formal classes are about decision problems, the intractability conclusions carry straight over to the optimisation problems engineers actually face.

---

Responding to Intractable Problems

If a problem is intractable, we cannot (as far as anyone knows) compute the exact optimal answer for large inputs in reasonable time — yet these problems (routing, scheduling, packing) are everywhere and must be tackled. The practical toolkit trades guaranteed optimality for feasibility.

Approach	What it does	Trade-off
Heuristics	Apply sensible rules of thumb to find a good (not provably optimal) solution quickly — e.g. "always visit the nearest unvisited city" for TSP	Fast and usually good, but with no guarantee of optimality
Approximation algorithms	Algorithms with a proven bound on how far from optimal they can be (e.g. "within 50% of the best")	Provable quality guarantee, but still not exact
Restricting the problem	Solve a special, easier case (e.g. TSP where distances obey the triangle inequality, or graphs of restricted structure)	Efficient, but only applies to the restricted instances
Exact methods for small $n$n	Use brute force or branch-and-bound when the input is small enough	Exact, but only feasible for small inputs
Randomised / metaheuristic search	Use randomness to explore the solution space — genetic algorithms, simulated annealing	Can escape poor local solutions, but results may vary between runs

The unifying idea is a deliberate, informed compromise: knowing a problem is intractable changes the goal from "the provably best answer" to "a good-enough answer, fast enough". A satnav, a delivery-routing system and a factory scheduler all run heuristics for exactly this reason — and they do so because the underlying problems are intractable, not in spite of it.

Worked Example: a Heuristic in Action