The Complexity Frontier: From Big O to P vs NP

Prologue

You write a function. It works perfectly on 100 elements. You deploy it in production. Six months later, the dataset has grown to 10 million records — and the function now runs for 47 hours. You changed nothing.

Vous écrivez une fonction. Elle fonctionne sur 100 éléments. Six mois plus tard, 10 millions de données, et elle tourne pendant 47 heures. Pas une ligne modifiée.

This isn't a bug. It's computational complexity revealing itself — the mathematical study of how resource consumption grows with problem size. Understanding it separates engineers who write code from those who design systems that scale.

This article traces the intellectual backbone of complexity theory: from the precise language of asymptotic notation, through the formal definition of complexity classes, to what is arguably the most important unsolved problem in all of science.

Part I — The Language of Growth: Asymptotic Notation

The Right Question

When we analyze an algorithm, the exact operation count is secondary. The question that matters is:

As $n \to \infty$, how does the cost function $T(n)$ behave?

This shift — from counting to characterizing — is the foundational move of complexity theory. It gives us a language to classify functions by their growth rate, independently of hardware, constants, and implementation details.

Big O: Upper Bound / Borne supérieure

Definition 1 (Big O).

En d'autres termes : $f$ est dominée par $g$ à partir d'un certain rang, à une constante multiplicative près. Ce qui compte, c'est la forme, pas le coefficient.

Proof (by example). Let $f(n) = 3n^2 + 7n + 42$. We claim $f(n) = O(n^2)$. For all $n \geq 1$: $7n \leq 7n^2$ and $42 \leq 42n^2$. Therefore:

With $c = 52$ and $n_0 = 1$, the definition is satisfied. The constant 52 is irrelevant — the growth shape is quadratic, and that's what Big O captures. $\blacksquare$

Big Omega and Theta: Completing the Picture

Observation (Big Omega and Theta). Big O gives an upper bound. Its counterpart, Big Omega, gives a lower bound:

This distinction matters in a subtle but important way. Proving that no comparison-based sorting algorithm can do better than $\Omega(n \log n)$ comparisons in the worst case tells us that Merge Sort is not merely good — it is optimal. The lower bound proof, not the upper bound, is what makes that claim.

When both bounds coincide, we write Big Theta:

Theta is the precise characterization — not "at most quadratic", but "genuinely, tightly quadratic".

The resulting hierarchy of growth rates looks like this:

Empirical Verification: Theory Meets Practice

The following benchmark makes the $O(n^2)$ vs $O(n \log n)$ gap concrete and measurable — not just abstract:

1function bubbleSort(arr: number[]): { sorted: number[]; ops: number } {
2  const a = [...arr];
3  let ops = 0;
4 
5  for (let i = 0; i < a.length; i++) {
6    for (let j = 0; j < a.length - i - 1; j++) {
7      ops++;
8      if (a[j] > a[j + 1]) [a[j], a[j + 1]] = [a[j + 1], a[j]];
9    }
10  }
11  return { sorted: a, ops };
12}
13 
14function mergeSort(arr: number[], ops = { count: 0 }): number[] {
15  if (arr.length <= 1) return arr;
16  const mid = Math.floor(arr.length / 2);
17  const left = mergeSort(arr.slice(0, mid), ops);
18  const right = mergeSort(arr.slice(mid), ops);
19  return merge(left, right, ops);
20}
21 
22function merge(left: number[], right: number[], ops: { count: number }): number[] {
23  const result: number[] = [];
24  let i = 0, j = 0;
25  while (i < left.length && j < right.length) {
26    ops.count++;
27    result.push(left[i] <= right[j] ? left[i++] : right[j++]);
28  }
29  return [...result, ...left.slice(i), ...right.slice(j)];
30}
31 
32// Benchmark
33[100, 1_000, 5_000, 10_000].forEach(n => {
34  const data = Array.from({ length: n }, () => Math.random() * 1000 | 0);
35  
36  const t1 = performance.now();
37  const { ops: bubbleOps } = bubbleSort(data);
38  const bubbleMs = performance.now() - t1;
39 
40  const mergeOps = { count: 0 };
41  const t2 = performance.now();
42  mergeSort(data, mergeOps);
43  const mergeMs = performance.now() - t2;
44 
45  console.log(
46    `n=${String(n).padStart(6)} | ` +
47    `Bubble: ${bubbleMs.toFixed(1)}ms (${bubbleOps} ops ≈ n²=${n**2}) | ` +
48    `Merge: ${mergeMs.toFixed(1)}ms (${mergeOps.count} ops ≈ n·log₂n=${Math.round(n * Math.log2(n))})`
49  );
50});

Sample output:

The theory predicts the practice with striking precision. Merge Sort's operation count tracks $n \log_2 n$ almost exactly across all sizes — not by coincidence, but because the recurrence relation $T(n) = 2T(n/2) + O(n)$ resolves to $\Theta(n \log n)$ by the Master Theorem.

Part II — Complexity Classes: What Problems Can Computation Solve?

The Class P

Une classe de complexité est un ensemble de problèmes partageant les mêmes ressources fondamentales nécessaires à leur résolution. For time complexity on deterministic machines, the central class is:

P is the class of decision problems solvable by a deterministic algorithm in polynomial time. The Cobham-Edmonds thesis — analogous to the Church-Turing thesis — argues that polynomial time captures what is feasibly computable. The numbers make the point:

Problems in P include sorting ($O(n \log n)$), shortest path via Dijkstra ($O((V+E) \log V)$), and — perhaps most surprisingly — primality testing, which the AKS algorithm (Agrawal, Kayal, Saxena, 2002) solved in $O((\log n)^{12})$. That last result shocked the community because primality had long been suspected to sit outside P.

The Class NP

This is where the theory becomes philosophically interesting.

Definition 2 (NP, verifier-based).

NP is the class of problems where a proposed solution can be verified efficiently, even if finding that solution may be hard. The asymmetry is the whole point.

La distinction fondamentale : vérifier une solution est facile ; en trouver une, potentiellement très difficile.

The canonical NP problem is 3-SAT: given a boolean formula in conjunctive normal form where each clause has exactly 3 literals, does a satisfying assignment exist?

Verifying a given assignment takes $O(n)$ — trivially polynomial. Finding one requires checking up to $2^n$ candidates naively.

NP-Completeness and Reductions

Definition 3 (Polynomial-time reduction). Formalizes the notion that one problem is "at least as hard" as another:

Definition 4 (NP-Complete). Problems that are the hardest in NP: every NP problem reduces to them in polynomial time. The Cook-Levin Theorem (1971) established that 3-SAT was the first such problem — a landmark result that unlocked the theory of NP-completeness.

From this, a cascade of reductions was discovered:

Hundreds of practically important problems — scheduling, routing, packing, planning — are NP-Complete.

Demo: The Exponential Wall

1from itertools import product
2from typing import List, Tuple
3 
4Clause = List[Tuple[int, bool]]
5Formula = List[Clause]
6 
7def verify_3sat(formula: Formula, assignment: dict) -> bool:
8    """Polynomial certificate check — O(clauses × literals_per_clause)."""
9    return all(
10        any(assignment[var] == pos for var, pos in clause)
11        for clause in formula
12    )
13 
14def solve_3sat_brute(formula: Formula, n_vars: int):
15    """Brute-force: O(2ⁿ · n). Infeasible for large n — that's the point."""
16    for i, values in enumerate(product([True, False], repeat=n_vars)):
17        assignment = {j + 1: v for j, v in enumerate(values)}
18        if verify_3sat(formula, assignment):
19            print(f"✓ SAT — found after {i+1} attempt(s) (max {2**n_vars})")
20            return assignment
21    print(f"✗ UNSAT — exhausted all {2**n_vars} assignments")
22    return None
23 
24# (x₁ ∨ ¬x₂ ∨ x₃) ∧ (¬x₁ ∨ x₂ ∨ ¬x₃) ∧ (x₁ ∨ x₂ ∨ x₃)
25formula = [
26    [(1, True),  (2, False), (3, True)],
27    [(1, False), (2, True),  (3, False)],
28    [(1, True),  (2, True),  (3, True)],
29]
30assignment = solve_3sat_brute(formula, n_vars=3)
31print(f"Assignment: {assignment}")
32print(f"Verified:   {verify_3sat(formula, assignment)}")
33 
34print("\n--- Scaling of 2ⁿ ---")
35for n in [10, 20, 30, 50, 100]:
36    print(f"n={n:3d} → {2**n:,} assignments")

Output:

At $n = 100$ variables, a solver checking $10^9$ assignments per second would require approximately $4 \times 10^{13}$ years. The observable universe is roughly $1.4 \times 10^{10}$ years old. The exponential wall is not an engineering problem — it is a mathematical one.

Part III — P vs NP: The Open Question

The Question

Listed among the seven Millennium Prize Problems by the Clay Mathematics Institute ($1,000,000 reward), this question has been open since Stephen Cook's 1971 paper. At its core:

Is finding always as hard as checking? Or does the asymmetry between search and verification reflect something fundamental about computation itself?

Est-ce que trouver est toujours aussi difficile que vérifier ? Ou cette asymétrie entre recherche et vérification révèle-t-elle quelque chose de fondamental sur la nature du calcul ?

The Two Scenarios

If P = NP: Every NP problem would admit a polynomial-time algorithm. The consequences would be profound. RSA encryption and elliptic-curve cryptography rely on the assumed hardness of integer factorization and discrete logarithm — problems in NP. A proof of P = NP would not immediately break them, but it would strongly suggest efficient algorithms exist. More broadly, mathematical proof verification would become automated, and optimization problems currently considered intractable would become tractable. Cook himself observed that such a world would be "a profoundly different place."

If P ≠ NP (the consensus belief): Some problems are inherently hard — no clever algorithm, no matter how ingeniously designed, will crack NP-Complete problems in polynomial time. This validates what practitioners already feel when they reach for approximation algorithms or heuristics.

More than 99% of complexity theorists believe P ≠ NP. Yet nobody has proved it. That gap between belief and proof is itself one of the deepest mysteries in mathematics.

Why the Proof Remains Elusive

Proving P ≠ NP requires showing that no polynomial-time algorithm can solve some NP-Complete problem. Not that we haven't found one — that none can exist. Three structural barriers have been identified, each ruling out entire families of proof techniques:

Observation 1 (Relativization - Baker, Gill, Solovay, 1975). There exist oracles $A$ and $B$ such that $P^A = NP^A$ but $P^B \neq NP^B$. Any proof technique that works uniformly for all oracles — which includes classical diagonalization — cannot resolve P vs NP either way.

Observation 2 (Natural Proofs - Razborov, Rudich, 1994). Most "natural" circuit lower bound techniques can be inverted into algorithms for breaking pseudorandom functions. If pseudorandom functions exist — which we believe they do precisely because we believe P ≠ NP — then natural proof techniques are provably insufficient.

Observation 3 (Algebrization - Aaronson, Wigderson, 2009). Algebraic extensions of relativization reveal a third barrier. Techniques powerful enough to prove IP = PSPACE are still insufficient to separate P from NP.

Any resolution of P vs NP requires a technique that simultaneously circumvents all three barriers. We do not yet know what such a technique looks like.

The Landscape of Classes

What is proven: $\mathbf{P} \subseteq \mathbf{NP} \subseteq \mathbf{PSPACE} \subseteq \mathbf{EXPTIME}$, and $\mathbf{P} \subsetneq \mathbf{EXPTIME}$ (by the Time Hierarchy Theorem). What remains open: whether any of the intermediate inclusions are strict. We can prove the gap between P and EXPTIME but not between P and NP, which sits immediately above it.

Practical Implications

Even without a resolution, complexity theory shapes practice daily. When a problem is identified as NP-Complete, it signals that exact polynomial-time solutions are almost certainly out of reach. The appropriate response is not to try harder — it is to reach for the right tool:

1// Subset Sum is NP-Complete.
2// For general inputs, this O(2ⁿ) brute-force is essentially unavoidable.
3function subsetSumBrute(arr: number[], target: number): number[] | null {
4  for (let mask = 0; mask < (1 << arr.length); mask++) {
5    const subset = arr.filter((_, i) => mask & (1 << i));
6    if (subset.reduce((a, b) => a + b, 0) === target) return subset;
7  }
8  return null;
9}
10 
11// But with bounded integer weights W, dynamic programming gives O(n · W).
12// This is "pseudo-polynomial" — polynomial in the value of W, not its bit-length.
13function subsetSumDP(arr: number[], target: number): number[] | null {
14  const dp = Array(target + 1).fill(false);
15  const parent: number[] = Array(target + 1).fill(-1);
16  dp[0] = true;
17 
18  for (const num of arr) {
19    for (let j = target; j >= num; j--) {
20      if (dp[j - num] && !dp[j]) {
21        dp[j] = true;
22        parent[j] = num;
23      }
24    }
25  }
26 
27  if (!dp[target]) return null;
28 
29  const result: number[] = [];
30  let rem = target;
31  while (rem > 0) {
32    result.push(parent[rem]);
33    rem -= parent[rem];
34  }
35  return result;
36}
37 
38// Understanding complexity tells you WHICH tool to reach for.
39// The wrong tool is not a matter of taste — it is a matter of feasibility.

The same principle extends to approximation algorithms (the PCP Theorem, 1992, shows that even approximating some NP-Hard problems within a constant factor is itself NP-Hard), randomized algorithms, and problem-specific heuristics. Knowing a problem's complexity class is not academic — it is the first design decision.

Epilogue

Complexity theory is the physics of computation. It tells us what is fundamentally possible and what isn't — not contingently, not for now, but provably and permanently.

La théorie de la complexité est la physique du calcul. Elle nous dit ce qui est fondamentalement possible — pas provisoirement, mais de manière prouvée et permanente.

When you know an algorithm is $O(n \log n)$, you know it will scale. When you recognize a problem as NP-Complete, you know to reach for approximation or special structure — not a faster computer. The knowledge changes the design decisions before a single line of code is written.

The P vs NP question remains open. At its core, it asks whether discovery is reducible to verification — whether the flash of insight that finds a proof can always be mechanized into a systematic search. We suspect it cannot. We cannot yet prove it.

That gap, between what we believe and what we can demonstrate, is one of the most beautiful things in science.

Written by Abdelbadie Khoubiza — CS student, full-stack developer, occasional mathematician. Taza, Morocco — February 2025.