Source: Section Notes 0, University of Michigan
Difficulty: Intermediate | Prerequisites: Proof Methods notes, basic algebra, familiarity with exponential and logarithmic functions.
Big-O notation is how computer scientists talk about how fast algorithms grow as inputs get larger. Instead of caring whether program A is 3 seconds faster than program B on today's laptop, we care whether A and B scale in fundamentally different ways. This is the language you will use for the rest of EECS 376 (and most of your CS career) whenever you analyse the efficiency of an algorithm. You should already be comfortable with basic algebra, exponents, and logarithms.
Big-O and its relatives (little-o, Big-Ω, little-ω, Θ) let you compare how functions grow without worrying about constant factors. Big-O is an asymptotic upper bound ("at most this fast"), Big-Ω is a lower bound ("at least this fast"), and Θ means both at once ("exactly this fast, up to constants"). The key intuition: a constant-factor slowdown is manageable, but an exponential blowup is not.
Asymptotic analysis
The study of how a function behaves as its input grows towards infinity, ignoring constant factors and lower-order terms. Think of it as the "zoomed-out" view of a function's growth.
Big-O, O(g(n))
An asymptotic upper bound. f(n) = O(g(n)) means f grows no faster than g, up to a constant multiple, for all sufficiently large n. In simple terms, "f is at most on the order of g".
Little-o, o(g(n))
A strict asymptotic upper bound. f(n) = o(g(n)) means f grows strictly slower than g. In simple terms, "f is eventually dwarfed by g".
Big-Omega, Ω(g(n))
An asymptotic lower bound. f(n) = Ω(g(n)) means f grows at least as fast as g, up to a constant multiple. In simple terms, "f is at least on the order of g".
Little-omega, ω(g(n))
A strict asymptotic lower bound. f(n) = ω(g(n)) means f eventually outpaces g by any constant factor.
Theta, Θ(g(n))
Asymptotic tight bound. f(n) = Θ(g(n)) means f(n) = O(g(n)) and f(n) = Ω(g(n)) simultaneously. In simple terms, "f grows at the same rate as g".
Each notation captures a different relationship between two functions as n → ∞. The analogy to ordinary inequalities helps:
O (Big-O) ≈ ≤ There exist constants M > 0 and n₀ such that for all n > n₀, |f(n)| ≤ M|g(n)|.
o (little-o) ≈ < For all M > 0 there exists n₀ such that for all n > n₀, |f(n)| < M|g(n)|.
Ω (Big-Omega) ≈ ≥ There exist constants M > 0 and n₀ such that for all n > n₀, |f(n)| ≥ M|g(n)|.
ω (little-omega) ≈ > For all M > 0 there exists n₀ such that for all n > n₀, |f(n)| > M|g(n)|.
Θ (Theta) ≈ = f(n) = O(g(n)) and f(n) = Ω(g(n)) both hold.
The critical difference between the "big" and "little" versions: Big-O and Big-Ω require you to find one constant M that works. Little-o and little-ω require the inequality to hold for every positive M, meaning the gap between the functions grows without bound.
What is the asymptotic relationship between f(n) = 2n and g(n) = eⁿ?
Answer: f(n) = o(g(n)), meaning 2n grows strictly slower than eⁿ.
To prove this, let n₀ = M + 1 for any positive M. Then eᴹ⁺¹ ≥ 2M(M + 1) holds for all positive M (you can verify with a graphing tool). So for any M, we can find an n₀ such that |f(n)| < M|g(n)| for all n > n₀.
Note: saying 2n = O(eⁿ) would also be true, since o implies O. But o(eⁿ) is the stronger, more informative statement. In practice, 2n = Θ(n) is the tightest useful bound: it tells you 2n grows linearly.
Answer: f(n) = Θ(n).
Showing O(n): We need M and n₀ such that 3n + 2 ln(n) ≤ Mn. Rearranging: (M − 3)n ≥ 2 ln(n). Set M = 4 and n₀ = 10, and verify n ≥ 2 ln(n) for n ≥ 10.
Showing Ω(n): Set M = 1 and n₀ = 1. Then 3n + 2 ln(n) > n for all n ≥ 1, since 2n + 2 ln(n) > 0.
Both directions hold, so f(n) = Θ(n).
Big-O: f(n) = O(g(n)) ⟺ ∃ M > 0, ∃ n₀ : ∀ n > n₀, |f(n)| ≤ M|g(n)|
Little-o: f(n) = o(g(n)) ⟺ ∀ M > 0, ∃ n₀ : ∀ n > n₀, |f(n)| < M|g(n)|
Big-Ω: f(n) = Ω(g(n)) ⟺ ∃ M > 0, ∃ n₀ : ∀ n > n₀, |f(n)| ≥ M|g(n)|
Little-ω: f(n) = ω(g(n)) ⟺ ∀ M > 0, ∃ n₀ : ∀ n > n₀, |f(n)| > M|g(n)|
Theta: f(n) = Θ(g(n)) ⟺ f(n) = O(g(n)) ∧ f(n) = Ω(g(n))
Big-O is how engineers decide whether an algorithm is practical at scale. If you are building a search engine that indexes billions of pages, the difference between an O(n log n) sorting algorithm and an O(n²) one is the difference between a query taking milliseconds and taking hours. When someone says "this algorithm is O(n)", they are telling you it scales linearly with input size, which is usually good news for large datasets.
Students often think Big-O gives the exact running time. It does not. O(n) means the function grows at most linearly; it says nothing about the actual constant factor or about behaviour on small inputs.
Saying f(n) = O(n²) when f(n) is actually Θ(n) is technically true but misleading. Always aim for the tightest bound you can prove.
Students sometimes confuse Big-O (upper bound) with Θ (tight bound). If an exam asks for "the" asymptotic complexity, they usually want Θ, not just O.
The notation f(n) = O(g(n)) uses "=" but it is not symmetric. You cannot flip it: O(g(n)) = f(n) is meaningless.
⚠️ Expect to prove asymptotic relationships from the definitions. This means finding explicit M and n₀ values (for Big-O and Big-Ω) or showing the condition holds for all M (for little-o and little-ω).
⚠️ Know the hierarchy: constants < log n < n < n log n < n² < 2ⁿ < n! and be able to prove any adjacent pair.
⚠️ When the question says "what is the asymptotic relationship", give the tightest notation. Θ is preferred over just O when both bounds hold.
⚠️ The course uses Big-O heavily in algorithm analysis later on. Comfort with these definitions now saves considerable time later.
True or false: 5n + 100 = O(n). (True. Set M = 6 and n₀ = 100.)
Fill in the blank: If f(n) = O(g(n)) and f(n) = Ω(g(n)), then f(n) = ____. (Θ(g(n)))
True or false: n² = o(n³). (True. n² grows strictly slower than n³.)
True or false: 2ⁿ = O(n¹⁰⁰). (False. Exponentials dominate any polynomial.)
Fill in the blank: Big-O is analogous to ____ while little-o is analogous to ____. (≤, <)
Q: Prove from the definition that 3n² + 7n = O(n²).
A: We need M and n₀ such that 3n² + 7n ≤ Mn² for all n > n₀. Dividing both sides by n²: 3 + 7/n ≤ M. For n ≥ 7, 7/n ≤ 1, so 3 + 7/n ≤ 4. Set M = 4, n₀ = 7.
Q: Is n³ = O(2ⁿ)? Justify.
A: Yes. For any polynomial p(n), there exists n₀ such that p(n) < 2ⁿ for all n > n₀. In fact, n³ = o(2ⁿ), the stronger statement. You can verify that for M = 1, setting n₀ = 10 gives n³ < 2ⁿ for all n > 10.
Q: What is the asymptotic relationship between f(n) = 5 log n and g(n) = n?
A: f(n) = o(g(n)). Logarithmic functions grow strictly slower than any polynomial. For any M > 0, 5 log n < Mn for all sufficiently large n.
Q: Prove that n = Ω(ln n).
A: Set M = 1 and n₀ = 1. For all n ≥ 1, n ≥ ln(n) because eⁿ ≥ n for all n ≥ 0, so n ≥ ln(n).
Big-O notation is used immediately in the next units of EECS 376 when analysing algorithm running times. It connects to the proof methods notes because establishing Big-O bounds often requires induction (e.g. proving that a recursive algorithm's running time satisfies a recurrence). Later, Big-O becomes central to complexity classes (P vs NP) and to understanding which problems are efficiently solvable.
Big-O notation, asymptotic analysis, time complexity, space complexity, little-o, Big-Omega, little-omega, Theta notation, asymptotic upper bound, asymptotic lower bound, tight bound, growth rate, polynomial time, exponential time, logarithmic growth, order of growth, algorithm efficiency, EECS 376, computational complexity