A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Algorithm analysis applies Big-O notation to classify algorithms by their time and space requirements as functions of input size n. Linear search is O(n); binary search is O(log n); comparison-based sorting is Ω(n log n), achieved by merge sort and heap sort. The complexity classes P (problems solvable in polynomial time) and NP (problems whose solutions are verifiable in polynomial time) frame the central open question of theoretical computer science: whether P = NP. NP-complete problems — the hardest problems in NP — include SAT, graph coloring, and Hamiltonian circuits.
Analyze familiar algorithms step by step, deriving their complexity by counting operations as a function of n. Understand binary search's O(log n) cost from the halving argument. Discuss P vs. NP conceptually: why verifying a solution is often easier than finding one.
You already know Big-O notation — the language for describing how an algorithm's resource use grows as input size grows. Algorithm complexity analysis applies that language systematically to compare algorithms and, at a deeper level, to classify the problems themselves. The key shift is from "how fast is this algorithm?" to "how fast *can* any algorithm for this problem be?"
Start with sorting. Algorithms like bubble sort and insertion sort run in O(n²) in the worst case: they compare each element against roughly every other element. Merge sort and heap sort achieve O(n log n) by exploiting divide-and-conquer structure — they split the problem, solve each half, and merge, doing O(n) merge work at O(log n) levels of recursion. The remarkable fact is that this is *optimal*: any comparison-based sorting algorithm must perform at least Ω(n log n) comparisons in the worst case. You can prove this with an information-theoretic argument — there are n! possible orderings of n elements, and each comparison eliminates at most half the possibilities, so you need at least log₂(n!) ≈ n log n comparisons to identify the correct one. No sorting algorithm that works only by comparison can do better.
Binary search achieves O(log n) by a different divide-and-conquer insight: at each step, it compares the target against the middle element and discards the half that cannot contain the target. Starting with n elements, each comparison halves the search space — after k comparisons, at most n/2k elements remain. You need k large enough that n/2k = 1, which gives k = log₂(n). Any algorithm that multiplicatively shrinks its remaining work at each step will have logarithmic complexity.
The classification of problems into complexity classes P and NP is one of the deepest open questions in mathematics. P is the class of problems solvable in polynomial time — O(nk) for some fixed k. NP is the class of problems whose *solutions can be verified* in polynomial time. Finding a Hamiltonian circuit (a path visiting every vertex exactly once) in a graph is hard — no polynomial algorithm is known. But if someone hands you a proposed circuit, you can verify in O(n) time that it visits every vertex exactly once. This asymmetry between finding and checking is what defines NP. Whether P = NP — whether every problem whose solution is easy to verify is also easy to solve — is unresolved. Most complexity theorists believe P ≠ NP, but no one has proved it.
NP-complete problems sit at the hardest end of NP: they are in NP, and every problem in NP can be reduced to them in polynomial time, meaning a polynomial algorithm for any NP-complete problem would imply P = NP. SAT (can a boolean formula be satisfied?), graph coloring, and the traveling salesman problem are all NP-complete. In practice, this means that if you encounter an NP-complete problem in an application, you should not expect to find an efficient exact algorithm — the field instead turns to approximation algorithms, heuristics, or exploiting special structure in real-world instances.