Before I can meaningfully compare two algorithms, I need a language for describing how their running time grows as the input gets larger. That’s exactly what asymptotic notation gives me. I don’t care that one algorithm takes 3 milliseconds and another takes 5 milliseconds on a tiny input — I care about how each one scales as $n$ grows into the millions or billions. This file is my reference for the notation, the common growth-rate functions I encounter constantly, and the intuition for how to compare them.
History and Background
Asymptotic notation, particularly Big-O notation, has its roots in number theory, introduced by German mathematician Paul Bachmann in 1894 and later popularized by Edmund Landau — which is why Big-O is sometimes called “Landau notation.” Computer scientist Donald Knuth is largely credited with adapting and popularizing this notation for algorithm analysis in the 1970s, especially through his multi-volume work The Art of Computer Programming, and his 1976 paper “Big Omicron and big Omega and big Theta,” which formalized the trio of notations ($O$, $\Omega$, $\Theta$) that I use constantly today.
Problem Statement
I want a rigorous, mathematically precise way to describe and compare the growth rates of functions — typically representing the running time or space usage of algorithms — as their input size $n$ grows toward infinity, while ignoring constant factors and lower-order terms that don’t matter for large inputs.
Core Concepts
- Big-O notation ($O$): An asymptotic upper bound — “grows no faster than.”
- Big-Omega notation ($\Omega$): An asymptotic lower bound — “grows no slower than.”
- Big-Theta notation ($\Theta$): A tight bound — “grows at exactly this rate,” combining both $O$ and $\Omega$.
- Little-o notation ($o$): A strict upper bound — “grows strictly slower than,” excluding equality in growth rate.
- Little-omega notation ($\omega$): A strict lower bound — “grows strictly faster than.”
- Common growth-rate hierarchy: From slowest to fastest growing, I typically encounter constant, logarithmic, linear, linearithmic, quadratic, cubic, polynomial, exponential, and factorial growth.
How It Works
When I want to classify a function $f(n)$ using asymptotic notation, I follow this process:
- I identify the dominant term of $f(n)$ as $n$ grows large, discarding lower-order terms and constant multipliers.
- I choose the appropriate notation ($O$, $\Omega$, or $\Theta$) depending on whether I want to express an upper bound, lower bound, or tight bound.
- I find witnesses — constants $c$ and $n_0$ — that satisfy the formal definition, proving the asymptotic relationship holds for all sufficiently large $n$.
Working Principle
The underlying mechanism is to abstract away hardware-specific and implementation-specific details (like exact constant factors, cache effects, or compiler optimizations) and focus purely on how the function’s growth rate compares to well-known reference functions as $n \to \infty$. This lets me meaningfully compare algorithms across different machines, languages, and implementations, since two implementations of the same $O(n \log n)$ algorithm will always eventually behave similarly at scale, even if their constant factors differ.
Mathematical Foundation
Big-O (upper bound):
$$ f(n) = O(g(n)) \iff \exists, c > 0,\ n_0 > 0 \text{ such that } 0 \leq f(n) \leq c \cdot g(n) \text{ for all } n \geq n_0 $$
Big-Omega (lower bound):
$$ f(n) = \Omega(g(n)) \iff \exists, c > 0,\ n_0 > 0 \text{ such that } 0 \leq c \cdot g(n) \leq f(n) \text{ for all } n \geq n_0 $$
Big-Theta (tight bound):
$$ f(n) = \Theta(g(n)) \iff \exists, c_1, c_2 > 0,\ n_0 > 0 \text{ such that } c_1 g(n) \leq f(n) \leq c_2 g(n) \text{ for all } n \geq n_0 $$
Little-o (strict upper bound):
$$ f(n) = o(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0 $$
Little-omega (strict lower bound):
$$ f(n) = \omega(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty $$
Common growth-rate hierarchy (from slowest to fastest):
$$ O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) $$
Example proof that $3n^2 + 5n + 2 = O(n^2)$: I need to find $c$ and $n_0$ such that $3n^2 + 5n + 2 \leq c n^2$ for all $n \geq n_0$. For $n \geq 1$, I have $5n \leq 5n^2$ and $2 \leq 2n^2$, so:
$$ 3n^2 + 5n + 2 \leq 3n^2 + 5n^2 + 2n^2 = 10n^2 $$
Choosing $c = 10$ and $n_0 = 1$ satisfies the definition, so $3n^2 + 5n + 2 = O(n^2)$.
Diagrams
flowchart TD
A["Function f(n)"] --> B{"Want upper, lower, or tight bound?"}
B -->|Upper bound| C["Use Big-O: f(n) ≤ c·g(n)"]
B -->|Lower bound| D["Use Big-Omega: f(n) ≥ c·g(n)"]
B -->|Tight bound| E["Use Big-Theta: c1·g(n) ≤ f(n) ≤ c2·g(n)"]
Pseudocode
Since asymptotic notation is a mathematical classification tool rather than an executable process, I represent the classification logic as pseudocode:
CLASSIFY-GROWTH(f, g):
ratio = f(n) / g(n) as n -> infinity
if ratio approaches a positive constant:
return "f(n) = Θ(g(n))"
else if ratio approaches 0:
return "f(n) = o(g(n))" // f grows strictly slower
else if ratio approaches infinity:
return "f(n) = ω(g(n))" // f grows strictly faster
else:
return "no simple asymptotic relationship (oscillating ratio)"
Step-by-Step Example
Let me classify $f(n) = 2n^2 + 3n$ against $g(n) = n^2$.
- I compute the ratio: $\dfrac{f(n)}{g(n)} = \dfrac{2n^2 + 3n}{n^2} = 2 + \dfrac{3}{n}$.
- As $n \to \infty$, $\dfrac{3}{n} \to 0$, so the ratio approaches exactly 2, a positive constant.
- Since the ratio approaches a positive constant, $f(n) = \Theta(n^2)$.
- I can also directly verify $f(n) = O(n^2)$ (choosing $c=5$, $n_0=1$) and $f(n) = \Omega(n^2)$ (choosing $c=2$, $n_0=1$), confirming the tight bound.
Time Complexity
Not applicable in the traditional sense — asymptotic notation is the tool I use to express time complexity, not an algorithm with its own running time. Classifying a given function’s growth rate is typically an $O(1)$ or simple calculus operation (taking a limit), done by hand or via symbolic computation.
Space Complexity
Not applicable, for the same reason — asymptotic notation is descriptive, not computational, so it has no memory footprint of its own.
Correctness Analysis
The correctness of any asymptotic classification depends on rigorously satisfying the formal definitions — finding valid witness constants $c$ (and $c_1, c_2$ for Theta) and a threshold $n_0$ beyond which the inequality holds for all larger $n$, not just some. A common trap is checking only a few small values of $n$ and assuming the pattern continues, when in fact the relationship might only hold asymptotically after some large threshold, or might not hold at all if a lower-order term happens to dominate for an unusually wide range of small $n$.
Advantages
- Provides a machine-independent, implementation-independent way to compare algorithms.
- Simplifies analysis by allowing me to ignore constant factors and lower-order terms that don’t matter at scale.
- Universally used and understood across the entire field of computer science, making it the standard language for algorithm analysis.
Disadvantages
- Ignores constant factors, which can matter enormously in practice — an algorithm with a huge constant factor might be slower than a “worse” asymptotic algorithm for realistic input sizes.
- Doesn’t capture real-world factors like cache behavior, memory hierarchy, or hardware-specific optimizations.
- Can be misapplied or misunderstood by beginners, especially confusing $O$ (upper bound, could be loose) with $\Theta$ (tight bound).
Applications
- Comparing algorithms during design and before implementation, to predict scalability.
- Technical interviews, where asymptotic notation is the standard language for discussing algorithm efficiency.
- Academic research papers, where formal complexity bounds are a core part of any algorithm’s presentation.
- Systems design, for reasoning about how a system will behave as data volume grows (e.g., database index lookups, network routing tables).
Implementation in C
Since asymptotic notation is a mathematical concept, I demonstrate it here with a small program that empirically measures how different growth-rate functions scale, helping build intuition for the differences between them.
#include <stdio.h>
#include <math.h>
/* Prints the values of several common growth-rate functions
for increasing n, to build intuition about their relative scale. */
int main() {
printf("%-10s %-12s %-12s %-14s %-14s %-16s\n",
"n", "log2(n)", "n", "n*log2(n)", "n^2", "2^n (capped)");
for (int n = 1; n <= 1024; n *= 2) {
double logn = (n == 1) ? 0 : log2((double)n);
double nlogn = n * logn;
double nsquared = (double)n * n;
double exp2n = (n <= 20) ? pow(2, n) : -1; /* avoid overflow for display */
printf("%-10d %-12.2f %-12d %-14.2f %-14.2f ", n, logn, n, nlogn, nsquared);
if (exp2n >= 0)
printf("%-16.0f\n", exp2n);
else
printf("%-16s\n", "(too large)");
}
return 0;
}
Sample Input and Output
n log2(n) n n*log2(n) n^2 2^n (capped)
1 0.00 1 0.00 1.00 2
2 1.00 2 2.00 4.00 4
4 2.00 4 8.00 16.00 16
8 3.00 8 24.00 64.00 256
16 4.00 16 64.00 256.00 65536
32 5.00 32 160.00 1024.00 (too large)
64 6.00 64 384.00 4096.00 (too large)
...
1024 10.00 1024 10240.00 1048576.00 (too large)
This table makes the growth-rate hierarchy tangible — by $n=1024$, $2^n$ is already astronomically larger than $n^2$, even though at $n=4$ they were comparable.
Optimization Techniques
- When comparing algorithms with the same asymptotic complexity, I look at the constant factors and lower-order terms, since these can matter for practical input sizes even though they’re ignored asymptotically.
- I use amortized analysis (a related but distinct technique) when an algorithm’s cost varies across operations but averages out over a sequence of operations — this often gives a tighter, more useful bound than worst-case-per-operation analysis.
- For algorithms with multiple parameters (not just $n$), I use multivariate asymptotic notation to capture how running time depends on each parameter independently.
Common Mistakes
- Using $O$ (upper bound) when $\Theta$ (tight bound) is what’s actually meant — saying “this algorithm is $O(n^2)$” when it’s actually $\Theta(n)$ is technically true but misleadingly loose.
- Forgetting that asymptotic notation describes behavior as $n \to \infty$, and inappropriately using it to reason about small, fixed input sizes where constant factors dominate.
- Sloppily dropping lower-order terms before rigorously establishing they don’t affect the classification — this is fine for “obvious” cases but should be justified for edge cases.
- Confusing algorithm running time with actual wall-clock time — two $O(n \log n)$ algorithms can have very different real-world performance due to constant factors.
Further Reading
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, Chapter 3: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- Knuth, D., “Big Omicron and Big Omega and Big Theta,” ACM SIGACT News, 1976: https://dl.acm.org/doi/10.1145/1008328.1008329
- Wikipedia, “Big O notation”: https://en.wikipedia.org/wiki/Big_O_notation
- MIT OpenCourseWare, “Asymptotic Notation” Lecture: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/
