Difficulty: Introductory to Intermediate | Prerequisites: Basic algebra, familiarity with logarithms, and an understanding of what a function is.
Asymptotic analysis is how computer scientists compare the efficiency of algorithms without getting bogged down in hardware specifics or constant factors. Big-O notation gives you a language for saying "this function grows no faster than that one" in a way that is precise enough to prove and general enough to be useful. This unit also introduces encoding and counting arguments, which are the first step toward understanding how information is represented and how many bits you need. These ideas recur throughout EECS 376, from complexity classes to lower bounds.
f(n) = O(g(n)) means f grows no faster than g, up to a constant multiplier, for all sufficiently large n. To prove it, find constants M and n₀ such that f(n) <= M · g(n) for all n >= n₀, or show that the limit of f(n)/g(n) is finite. A program that ignores its input runs in O(1). To encode n distinct items with strings of length k over an alphabet of size s, you need k = ⌈logₛ(n)⌉.
Big-O notation, O(g(n))
f(n) = O(g(n)) means there exist positive constants M and n₀ such that for all n >= n₀, f(n) <= M · g(n). Think of it as: "f grows at most as fast as g, ignoring constant factors and small inputs."
Little-o notation, o(g(n))
f(n) = o(g(n)) means f grows strictly slower than g. Formally, the limit of f(n)/g(n) as n approaches infinity equals 0. In simple terms, g eventually dwarfs f completely.
Asymptotic bound
A characterisation of how a function behaves as its input grows toward infinity, ignoring constant multipliers and finitely many exceptions. It tells you the growth rate, not the exact value.
Constant time, O(1)
A running time that does not depend on the size of the input at all. The program may still do work, but the amount of work is bounded by a fixed number regardless of n.
Logarithm (base 2)
log₂(n) is the power to which you raise 2 to get n. Logarithms grow very slowly: log₂(1,000,000) is roughly 20. Key identity: log₂(nᵏ) = k · log₂(n).
L'Hopital's rule
A technique for evaluating limits of the form 0/0 or ∞/∞: take derivatives of the numerator and denominator separately and re-evaluate the limit. Used here to compare (log n)³ against 2^(log n) = n.
Quaternary string
A string over a 4-symbol alphabet (e.g. {a, b, c, d}). The number of distinct strings of length k is 4ᵏ.
Encoding length
The minimum string length k needed to represent n distinct items using an alphabet of size s. Equals ⌈logₛ(n)⌉ because sᵏ must be at least n.
f(n) = O(g(n)) if and only if there exist constants M > 0 and n₀ >= 0 such that for all n >= n₀, f(n) <= M · g(n).
Two standard proof strategies:
Direct: Find explicit values of M and n₀ that work, and verify the inequality.
Limit test: Show lim(n→∞) f(n)/g(n) is a finite number (possibly 0). If the limit is 0, you also get f(n) = o(g(n)), the stronger statement that f grows strictly slower.
4a: f(n) = n + log₂(n⁴), g(n) = (1/9)n - 5
Simplify: log₂(n⁴) = 4 log₂(n), and 4 log₂(n) < 4n for all n >= 1. So f(n) < 5n.
Need 5n <= M · ((1/9)n - 5) for large n. Setting M = 90 and n₀ = 90 works: 5n <= 10n - 450 = 90((1/9)n - 5) holds for n > 27.
Result: f(n) = O(g(n)). Yes.
4b: f(n) = (3n)³, g(n) = n³
f(n) = 27n³, so f(n) <= 27 · g(n) for all n >= 1.
M = 27, n₀ = 1. Done immediately.
Result: f(n) = O(g(n)). Yes.
4c: f(n) = (log₂ n)³, g(n) = 2^(log₂ n) = n
Use the limit test with the substitution m = log₂ n (so n → ∞ becomes m → ∞).
lim(m→∞) m³ / 2ᵐ. Apply L'Hopital's rule three times: 3m² / (2ᵐ ln 2) → 6m / (2ᵐ (ln 2)²) → 6 / (2ᵐ (ln 2)³) → 0.
Result: f(n) = O(g(n)), and in fact f(n) = o(g(n)). Any polynomial of log n grows slower than n.
4d: f(n) = 2^(1.4n), g(n) = 3eⁿ
lim(n→∞) 2^(1.4n) / (3eⁿ) = lim(n→∞) (2^1.4)ⁿ / (3 · eⁿ) = lim(n→∞) (2.639)ⁿ / (3 · 2.718ⁿ).
Since 2.639 < 2.718, the ratio shrinks to 0.
Result: f(n) = O(g(n)), and f(n) = o(g(n)). The base of the exponential determines everything.
4e: f(n) = log₂(2n), g(n) = log₂(n)
log₂(2n) = log₂(2) + log₂(n) = 1 + log₂(n).
For n >= 3, 1 + log₂(n) <= 2 · log₂(n). So M = 2, n₀ = 3.
Result: f(n) = O(g(n)). Yes. A constant additive term inside a log does not change the growth rate.
Logarithmic functions grow slower than any polynomial: (log n)ᵏ = O(n) for any fixed k.
A polynomial grows slower than any exponential: nᵏ = O(cⁿ) for any c > 1.
Among exponentials, the one with the larger base dominates: aⁿ = O(bⁿ) when a < b.
Constant factors inside a function do not affect Big-O: (3n)³ = O(n³).
The program loops 376 times, prints a message, and returns 0. It never looks at its input X.
Because the loop count is a fixed constant (376) and the print operation takes some fixed time per call, the total running time is bounded by a constant regardless of the input size. The program runs in O(1), or "constant time."
Complexity is measured as a function of the input size. If the program's behaviour does not depend on the input at all, the running time is constant. It does not matter that the loop runs 376 times rather than once: 376 is still a constant, not a function of n.
You have n items to label, and your alphabet has 4 symbols. Each string of length k gives you 4ᵏ distinct labels (4 choices per position, k positions). You need enough labels for all n items, so:
4ᵏ >= n, which means k >= log₄(n).
Since k must be an integer, the smallest valid k is ⌈log₄(n)⌉ (the ceiling of log base 4 of n).
For an alphabet of size s and n items, the minimum string length is ⌈logₛ(n)⌉. When s = 2 (binary), this gives ⌈log₂(n)⌉ bits, which is the standard formula for the number of bits needed to represent n distinct values. This is the foundation of information-theoretic lower bounds.
Logarithm of a power:
log₂(nᵏ) = k · log₂(n). This converts a polynomial inside a log into a constant multiplier outside.
Logarithm of a product:
log₂(ab) = log₂(a) + log₂(b). Used in 4e to split log₂(2n) into 1 + log₂(n).
Logarithm grows slower than any polynomial:
For any fixed k, (log₂ n)ᵏ = o(n). This is the key fact behind 4c.
Exponential growth comparison:
If 1 < a < b, then aⁿ = o(bⁿ). The ratio (a/b)ⁿ → 0 because a/b < 1.
L'Hopital's rule (for ∞/∞):
If both f(x) and g(x) → ∞ as x → ∞, then lim f(x)/g(x) = lim f'(x)/g'(x), provided the latter limit exists. Apply repeatedly until the numerator or denominator stabilises.
Encoding formula:
Minimum string length over an alphabet of size s for n items: k = ⌈logₛ(n)⌉.
Students often think Big-O gives an exact running time. It does not. O(n²) means the running time is at most proportional to n², not that it equals n².
Students confuse Big-O (upper bound) with Big-Theta (tight bound). Saying f(n) = O(n²) does not rule out f being O(n) as well. Big-O is a ceiling, not a label.
A common mistake is to say a program with a fixed loop (like 376 iterations) is O(n) because "it loops." If the loop count does not depend on the input, the running time is O(1).
Students sometimes believe that if f(n) = O(g(n)) then g(n) = O(f(n)). This is false. Big-O is not symmetric. Example: n = O(n²), but n² is not O(n).
True or false: f(n) = O(g(n)) means f(n) <= g(n) for all n.
False. It means f(n) <= M · g(n) for some constant M, and only for n >= n₀.
Fill in the blank: log₂(n⁴) simplifies to ___.
4 log₂(n).
True or false: A program that runs a for-loop exactly 1,000 times, regardless of input, has O(1) complexity.
True. The loop count is a constant.
Fill in the blank: To represent 100 items using strings from a 4-letter alphabet, the minimum string length is ⌈log₄(___)⌉.
True or false: (log n)¹⁰⁰ = O(n).
True. Any polynomial of log n grows slower than n.
Q: Is f(n) = 5n² + 3n + 7 equal to O(n²)? Prove it.
A: Yes. For n >= 1, 5n² + 3n + 7 <= 5n² + 3n² + 7n² = 15n². So M = 15, n₀ = 1.
Q: Is f(n) = n³ equal to O(n²)?
A: No. Suppose for contradiction n³ <= M · n² for all large n. Dividing both sides by n² gives n <= M, which fails for n > M.
Q: What is the running time of a function that reads every element of its input array once and does O(1) work per element?
A: O(n), where n is the length of the array.
Q: How many bits do you need to encode 1,000,000 distinct items?
A: ⌈log₂(1,000,000)⌉ = ⌈19.93⌉ = 20 bits.
Q: Show that 2ⁿ = o(3ⁿ).
A: lim(n→∞) 2ⁿ/3ⁿ = lim(n→∞) (2/3)ⁿ = 0, since 2/3 < 1. Therefore 2ⁿ = o(3ⁿ).
Big-O notation is the language you will use in every algorithm analysis in EECS 376 and beyond: reductions, complexity classes (P, NP), and space complexity all build on it. The encoding/counting argument from the quaternary string problem is a precursor to Kolmogorov complexity and information-theoretic lower bounds. L'Hopital's rule, while a calculus technique, appears routinely in comparing growth rates of algorithms, especially when logarithmic and exponential functions are involved.
Big-O notation, Big-Omega, Big-Theta, little-o, asymptotic analysis, growth rate, constant time, logarithmic time, polynomial time, exponential time, L'Hopital's rule, limit comparison, quaternary encoding, binary encoding, encoding length, alphabet size, string length, counting argument, information theory, EECS 376, foundations of computer science, University of Michigan