Difficulty: Intermediate | Prerequisites: Basic algebra, familiarity with limits and functions of n.
Asymptotic notation is the language computer scientists use to describe how an algorithm's running time (or space) scales as input size grows. Rather than counting exact operations, you classify growth rate, which lets you compare algorithms and predict performance on large inputs. This material sits at the foundation of algorithm analysis and comes back in every algorithms course and technical interview. You should already be comfortable with basic algebra, polynomials, and the intuition behind limits.
Big-O (O) gives an upper bound on growth, Big-Omega (Ω) gives a lower bound, and Big-Theta (Θ) gives a tight bound where both apply. For a polynomial with a positive leading coefficient, the asymptotic class is determined entirely by the highest-degree term. Always aim for the tightest bound you can prove.
Big-O notation, O(g(n))
A function f(n) is O(g(n)) if there exist positive constants c and n₀ such that f(n) ≤ c · g(n) for all n ≥ n₀.
Think of it as: an asymptotic ceiling. f never grows faster than g, up to a constant factor, once n is large enough.
Big-Omega notation, Ω(g(n))
A function f(n) is Ω(g(n)) if there exist positive constants c and n₀ such that f(n) ≥ c · g(n) for all n ≥ n₀.
Think of it as: an asymptotic floor. f grows at least as fast as g, up to a constant factor.
Big-Theta notation, Θ(g(n))
A function f(n) is Θ(g(n)) if there exist positive constants c₁, c₂, and n₀ such that c₁ · g(n) ≤ f(n) ≤ c₂ · g(n) for all n ≥ n₀.
Think of it as: a tight sandwich. f grows at exactly the same rate as g. You need both an upper and a lower bound with the same g(n).
Asymptotic growth rate
The rate at which a function's value increases as its input approaches infinity, ignoring constant factors and lower-order terms.
In simple terms, this means: how fast does the running time blow up when you double or triple the input size?
Dominant term
The term in a polynomial (or sum) that grows fastest and therefore determines the function's asymptotic class. For aₘnᵐ + ... + a₁n + a₀, the dominant term is aₘnᵐ.
In simple terms, this means: the one piece of the expression that matters when n gets big, because everything else becomes negligible by comparison.
f(n) = O(g(n)) means g(n) is an asymptotic upper bound on f(n).
You need to find constants c > 0 and n₀ such that f(n) ≤ c · g(n) for all n ≥ n₀.
The rule: pick g(n) as small as possible. 3n + 3 = O(n) is the useful statement, even though 3n + 3 = O(n²) is also technically correct.
Example: 3n + 3 = O(n), because 3n + 3 ≤ 4n for all n ≥ 3 (here c = 4, n₀ = 3).
f(n) = Ω(g(n)) means g(n) is an asymptotic lower bound on f(n).
You need constants c > 0 and n₀ such that f(n) ≥ c · g(n) for all n ≥ n₀.
The rule: pick g(n) as large as possible. 3n + 2 = Ω(n) is more informative than 3n + 2 = Ω(1).
Examples:
3n + 2 = Ω(n), since 3n + 2 ≥ 3n for n ≥ 1.
6 · 2ⁿ + n² = Ω(2ⁿ), since 6 · 2ⁿ + n² ≥ 6 · 2ⁿ for n ≥ 1.
10n⁴ + 4n = Ω(n⁴).
f(n) = Θ(g(n)) means g(n) is both an upper and lower bound: f can be "sandwiched" between c₁ · g(n) and c₂ · g(n).
Equivalently, f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)).
Examples:
3n + 2 = Θ(n), because 3n ≤ 3n + 2 ≤ 4n for n ≥ 2.
10n² + 4n + 2 = Θ(n²).
6 · 2ⁿ + n² = Θ(2ⁿ).
Key distinction: 10n² + 4n + 2 = O(n³) is true, but 10n² + 4n + 2 ≠ Θ(n³). You cannot sandwich a quadratic between two cubics. Likewise, 10n² + 4n + 2 = Ω(n) is true, but 10n² + 4n + 2 ≠ Θ(n).
If f(n) = aₘnᵐ + aₘ₋₁nᵐ⁻¹ + ... + a₁n + a₀ and aₘ > 0, then:
f(n) = O(nᵐ) (provided all coefficients aᵢ ≥ 0)
f(n) = Ω(nᵐ) (provided aₘ > 0)
f(n) = Θ(nᵐ) (provided aₘ > 0)
The highest-degree term with a positive coefficient determines the asymptotic class. All lower-order terms become negligible.
Functions ranked from slowest to fastest growth:
1 ≺ log log n ≺ log n ≺ nᵋ ≺ nᶜ ≺ n^(log n) ≺ cⁿ ≺ nⁿ ≺ c^(cⁿ)
Here ε is an arbitrary constant with 0 < ε < 1, and c is an arbitrary constant with 1 < c. The relation f(n) ≺ g(n) means lim(n→∞) f(n)/g(n) = 0, i.e. f grows strictly slower than g.
All these functions (except 1) go to infinity; the question is not whether they become infinite, but how fast.
O(1): constant time
O(n): linear
O(n²): quadratic
O(n³): cubic (and in general, polynomial)
O(2ⁿ): exponential
f(n) = O(g(n)) \iff \exists\, c > 0,\, n_0 > 0 \text{ s.t. } f(n) \le c \cdot g(n) \;\forall\, n \ge n_0f(n) = \Omega(g(n)) \iff \exists\, c > 0,\, n_0 > 0 \text{ s.t. } f(n) \ge c \cdot g(n) \;\forall\, n \ge n_0f(n) = \Theta(g(n)) \iff \exists\, c_1, c_2 > 0,\, n_0 > 0 \text{ s.t. } c_1 g(n) \le f(n) \le c_2 g(n) \;\forall\, n \ge n_0f(n) \prec g(n) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0\text{Polynomial theorem: } f(n) = a_m n^m + \cdots + a_1 n + a_0,\; a_m > 0 \implies f(n) = \Theta(n^m)Students often think Big-O gives you the exact growth rate. It does not. Big-O is only an upper bound. Saying f(n) = O(n²) does not mean the function is quadratic; it means it grows no faster than quadratic. The tight characterisation comes from Θ.
Students confuse "correct" with "useful." Saying 3n + 3 = O(n²) is technically true but unhelpful, because it is not the tightest upper bound. Always state the tightest O you can prove.
Students assume Θ and O are interchangeable. They are not. Θ(n²) tells you both the ceiling and the floor. O(n²) only tells you the ceiling. If you know Θ, you know O and Ω as well, but the reverse is not true.
Students forget the "for all n ≥ n₀" condition. The bound does not need to hold for small n. Constants and thresholds exist specifically to let you ignore small-input behaviour.
⚠️ Expect to be asked: "Is f(n) = Θ(g(n))?" where f is a polynomial and g is a different degree. You must show the sandwich fails (the lower bound breaks).
⚠️ A classic exam move: giving a function like 10n² + 4n + 2 and asking whether it is Θ(n³). You can show it is O(n³) but not Ω(n³), so the tight bound fails.
⚠️ The polynomial theorem is a shortcut. If you can identify the leading term and its coefficient is positive, you can write down Θ(nᵐ) immediately without finding explicit constants.
⚠️ Know the growth hierarchy cold. Exam questions often ask you to rank functions by growth rate or determine which Big-O class a given expression belongs to.
True or false: If f(n) = O(n²), then f(n) = O(n³). True. O(n²) ⊆ O(n³) because any function bounded by cn² is also bounded by cn³.
True or false: If f(n) = Θ(n), then f(n) = Θ(n²). False. Θ requires both upper and lower bounds with the same g(n). A linear function cannot be lower-bounded by n².
Fill in the blank: For f(n) = 7n³ + 2n + 5, f(n) = Θ(___). n³. The leading term's degree is 3 and the coefficient is positive.
True or false: 2ⁿ = O(n¹⁰⁰). False. Exponential growth outpaces any polynomial.
Fill in the blank: The relation f(n) ≺ g(n) means lim(n→∞) f(n)/g(n) = ___. 0.
Q: Prove that 3n + 2 = Θ(n).
A: Lower bound: 3n + 2 ≥ 3n for all n ≥ 1, so 3n + 2 = Ω(n) with c = 3, n₀ = 1. Upper bound: 3n + 2 ≤ 4n for all n ≥ 2, so 3n + 2 = O(n) with c = 4, n₀ = 2. Since both hold, 3n + 2 = Θ(n).
Q: Is 10n² + 4n + 2 = Θ(n³)? Justify your answer.
A: No. The upper bound holds (10n² + 4n + 2 = O(n³)), but the lower bound fails. For any c₁ > 0, c₁n³ eventually exceeds 10n² + 4n + 2, so the function is not Ω(n³). The tight bound is Θ(n²).
Q: Rank the following in order of growth rate: n², 2ⁿ, log n, n log n, 1, n.
A: 1 ≺ log n ≺ n ≺ n log n ≺ n² ≺ 2ⁿ.
Q: What is the running time of two nested for-loops, each running from 1 to n?
A: O(n²). The outer loop runs n times, and for each iteration the inner loop runs n times, giving n × n = n² operations.
Q: If f(n) = O(n) and g(n) = O(n²), what is f(n) + g(n)?
A: O(n²). The sum is dominated by the larger term. By the addition rule, O(f(n)) + O(g(n)) = O(max(|f(n)|, |g(n)|)).
This material connects directly to algorithm design (CS 182 and beyond): every time you analyse a sorting algorithm, a graph traversal, or a divide-and-conquer recurrence, you express the result in Big-O, Ω, or Θ. The growth hierarchy reappears when you study recurrence relations and the Master Theorem. Understanding tight bounds is also essential for amortised analysis, where you prove that a sequence of operations stays within a given bound on average.
asymptotic analysis, Big-O notation, Big-Omega notation, Big-Theta notation, upper bound, lower bound, tight bound, growth rate, time complexity, running time classification, polynomial theorem, dominant term, order of growth, asymptotic growth ratio, CS 182, Purdue, Foundations of Computer Science, algorithm complexity, constant time, linear time, quadratic time, exponential time, O(n), O(n²), O(log n), Θ(n), Ω(n)