A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Standard complexity classes ordered by growth: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n), O(n²) quadratic, O(2n) exponential, O(n!) factorial. Each class represents fundamentally different algorithm scalability and feasibility on large inputs.
You already know that big-O notation describes how an algorithm's runtime grows relative to input size n. Complexity classes organize that idea into a hierarchy of qualitatively different behaviors. The key insight is that these classes are not just faster or slower versions of each other — they represent fundamentally different scalability. An O(n²) algorithm and an O(n) algorithm are not just "one slower" — at n = 1,000,000, the O(n) algorithm might take a second while the O(n²) takes 11 days.
Start at the bottom of the hierarchy. O(1) constant time means the algorithm takes the same effort regardless of input size — looking up an element in a hash table, or reading the first item of a list. O(log n) logarithmic time is nearly as good: binary search on a sorted list of a billion items takes about 30 comparisons, because each comparison halves the remaining search space. Any time you can discard half the problem at each step, you get a logarithm. O(n) linear time means you must touch every element once — scanning a list for a value, computing a sum. This is the natural floor for problems that require reading all their input.
The middle classes represent common algorithmic tradeoffs. O(n log n) is the complexity of efficient comparison-based sorting algorithms (merge sort, heapsort). It's the cost of repeatedly halving — you do O(log n) work, and you must do it for each of the O(n) elements. O(n²) quadratic arises from nested loops over the input — comparing every element to every other element. Bubble sort and insertion sort are O(n²). For n = 10,000 items, that's 100 million operations — still manageable. At n = 1,000,000, it's a trillion.
The upper classes are qualitatively infeasible for large inputs. O(2n) exponential means the work doubles with each additional element. Brute-force search over all subsets of n items, solving the traveling salesman problem by checking all routes — these are O(2n). For n = 50, that's over a quadrillion operations. O(n!) factorial is worse still — generating all permutations of n items. For n = 20, that's over 2 quintillion operations. These classes are not just "slow" — they are computationally intractable for any realistic input. The dividing line between polynomial time (O(nk) for some fixed k) and superpolynomial time (O(2n), O(n!)) is the central distinction in theoretical computer science, and it motivates the entire P vs NP question.