Don't Panic — Computational Complexity

Computational complexity is the part of computer science that asks what a calculation costs as its input grows. It is not a stopwatch with academic robes. A stopwatch tells you what one program did on one machine. Complexity asks what an algorithm must spend under a stated model, which is less relaxing and more useful.

The first trap is the word “size.” An integer that looks enormous may take few bits to write down. A graph has vertices and edges. Until the input encoding is named, an expression such as O(n²) has brought a variable to a meeting without introducing it. The second trap is the resource: time is familiar, but memory, randomness, communication, and circuit size also take turns being expensive.

Asymptotic analysis studies growth after inputs become large. Big O supplies an upper bound; Big Omega supplies a lower bound; Big Theta says the two meet. These labels do not tell you whether the claim is worst case, average case, or best case. Nor do they promise that a polynomial is quick or that an exponential method is useless. Constants, degree, structure, and actual input range all insist on being invited back in.

Then comes P and NP, two labels that have acquired more folklore than they requested. P holds decision problems that a deterministic algorithm solves in polynomial time. NP holds those whose yes answers have certificates that can be checked in polynomial time. P sits inside NP. Whether the two are equal remains open, so no one has permission to write “NP means impossible” on the whiteboard.

A reduction is the arrow that keeps the map honest. To show a target problem is hard, transform a known hard problem into that target. A fast target solver would then solve the source quickly too. Reverse the arrow and you may have found an algorithmic route, which is good news, but it is not a hardness proof. The arrow has standards.

When exact worst-case work is too costly, the course does not hand you a ceremonial resignation letter. Restrict the input family, isolate a small parameter, use an approximation with a stated guarantee, or use a measured heuristic. The Cheatsheet holds compact rules; Slides show the map; Reference continues into reductions and lower bounds. Start by naming the input, model, resource, and case. The notation becomes less mysterious once it has something precise to describe.

Don't Panic — Computational Complexity

Relevant careers