A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Asymptotic notation describes how algorithms' time and space usage scales with input size. Big-O provides an upper bound, Big-Omega a lower bound, and Big-Theta a tight bound. These notations ignore constant factors and focus on dominant growth rates.
Start with concrete examples: n² grows faster than n log n, which grows faster than n. Draw or sketch growth curves. Compare 2n vs n² for small values (n=10, 100, 1000) to see the difference. Practice classifying simple code snippets (loops, nested loops, recursion).
From your work on algorithm design basics, you have written algorithms and observed that some are faster than others. But "faster" is slippery — an algorithm that wins on 100 elements might lose on a million, and raw timing depends on your hardware. Asymptotic notation gives you a hardware-independent language for talking about how algorithms scale. The core question it answers is: as the input grows toward infinity, how does the resource usage grow?
Big-O notation (O) provides an upper bound on growth. When we say an algorithm is O(n²), we mean its runtime grows no faster than some constant times n², once n is large enough. Formally, f(n) is O(g(n)) if there exist constants c > 0 and n₀ such that f(n) ≤ c · g(n) for all n ≥ n₀. The constants c and n₀ absorb the specifics — the exact number of operations per loop iteration, the speed of your CPU, the overhead of function calls. What remains is the shape of the growth curve. This is why O(2n) and O(n) are the same: the factor of 2 is absorbed into the constant c.
Big-Omega (Ω) is the mirror image: a lower bound. f(n) is Ω(g(n)) means f(n) grows at least as fast as g(n) for large inputs. If an algorithm is Ω(n log n), no input of size n can make it run faster than n log n (up to constants). Big-Theta (Θ) combines both: f(n) is Θ(g(n)) means it is both O(g(n)) and Ω(g(n)) — the growth rate is tightly bounded from above and below. When someone says "merge sort is Θ(n log n)," they mean it always grows proportionally to n log n, never significantly faster or slower.
A helpful analogy: Big-O is like saying "this package weighs at most 10 kg." Big-Omega says "it weighs at least 5 kg." Big-Theta says "it weighs between 5 and 10 kg." In practice, Big-O is used most often because programmers care about worst-case guarantees — you want to know your algorithm will not blow up, even on adversarial inputs. But when you can establish a Θ bound, it is more informative because it pins down the growth rate precisely. The common complexity classes you will encounter — O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) — form a hierarchy where each grows strictly faster than the one before it, and recognizing which class an algorithm falls into is the first step in evaluating whether it is practical for a given problem size.