Difficulty: Intermediate | Prerequisites: Part 1 of these notes (proof techniques, induction). Familiarity with limits and basic algebra of logarithms and exponents.
Asymptotic notation is the formal language EECS 376 uses to talk about how fast algorithms grow as input size increases. Rather than measuring exact running times (which depend on hardware and constants), Big-O, Big-Omega, and Big-Theta classify functions by their growth rate. Euclid's algorithm for computing the greatest common divisor is one of the earliest algorithms you will analyse with these tools. If you are comfortable with limits and can handle basic algebraic manipulation of logarithms and exponentials, you are ready for this material.
Big-O gives an asymptotic upper bound on a function's growth, Big-Omega gives a lower bound, and Big-Theta means the function grows at exactly that rate (both upper and lower). You can prove these relationships either by finding explicit constants c and n₀, or by taking the limit of f(n)/g(n). Euclid's algorithm computes the GCD by repeated division, and consecutive Fibonacci-like inputs force the most iterations.
Big-O notation, O(g(n))
f(n) = O(g(n)) means g(n) is an asymptotic upper bound on f(n). Formally: there exist positive constants c and n₀ such that f(n) ≤ c · g(n) for all n ≥ n₀. In simple terms, f grows no faster than g, up to a constant factor, once n is large enough.
Big-Omega notation, Ω(g(n))
f(n) = Ω(g(n)) means g(n) is an asymptotic lower bound on f(n). Formally: there exist positive constants c and n₀ such that f(n) ≥ c · g(n) for all n ≥ n₀. In simple terms, f grows at least as fast as g.
Big-Theta notation, Θ(g(n))
f(n) = Θ(g(n)) means g(n) is an asymptotic tight bound. f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)). Think of it as: f and g grow at the same rate.
Limit lemma for Big-O (Lemma 4)
When lim(n→∞) f(n)/g(n) exists or is infinite: f(n) = O(g(n)) if and only if that limit is finite. Important caveat: the limit does not need to exist for f(n) = O(g(n)) to hold.
Limit lemma for Big-Omega (Lemma 5)
When lim(n→∞) f(n)/g(n) exists or is infinite: f(n) = Ω(g(n)) if and only if the limit is greater than zero (including infinite). Same caveat: the limit need not exist.
Greatest common divisor (GCD)
The largest positive integer that divides both a and b. Euclid's algorithm computes this by repeated application of the division algorithm.
Euclid's algorithm
To compute GCD(a, b): repeatedly replace the larger number with the remainder of dividing it by the smaller, until the remainder is 0. The last non-zero remainder is the GCD. In simple terms, keep dividing and taking remainders until one side hits zero.
The definitions, side by side
All three notations follow the same template: "there exist constants c > 0 and n₀ > 0 such that [inequality] for all n ≥ n₀."
O(g(n)): f(n) ≤ c · g(n). Upper bound.
Ω(g(n)): f(n) ≥ c · g(n). Lower bound.
Θ(g(n)): both O and Ω hold (possibly with different constants). Tight bound.
Two ways to prove an asymptotic relationship
Definition method: Find explicit values of c and n₀ that satisfy the inequality. This is a direct proof.
Limit method: Compute lim(n→∞) f(n)/g(n). If the limit is finite and non-zero, f = Θ(g). If finite (including zero), f = O(g). If positive (including infinite), f = Ω(g).
Worked example: log_a(n) vs. log_b(n)
For constants a, b > 1: is log_a(n) = O(log_b(n))?
By the change-of-base formula, log_a(n) = log_b(n) / log_b(a). So log_a(n) / log_b(n) = 1/log_b(a), which is a positive finite constant. The limit is finite, so log_a(n) = O(log_b(n)). The limit is also positive, so log_a(n) = Ω(log_b(n)), and therefore log_a(n) = Θ(log_b(n)).
The takeaway: logarithm base does not matter for asymptotic analysis. All logarithms differ by a constant factor.
Worked example: 4ⁿ vs. 2ⁿ
Is 4ⁿ = O(2ⁿ)?
lim(n→∞) 4ⁿ/2ⁿ = lim(n→∞) (4/2)ⁿ = lim(n→∞) 2ⁿ = ∞.
The limit is infinite (not finite), so 4ⁿ ≠ O(2ⁿ). However, the limit is greater than zero, so 4ⁿ = Ω(2ⁿ). In plain terms, 4ⁿ grows strictly faster than 2ⁿ.
Comparing O(n log n) and O(n²) running times
The worksheet asks: does an O(n log n) algorithm always run faster than an O(n²) algorithm on the same input?
The answer is "some." Big-O is an upper bound, not an exact running time. An algorithm that is O(n log n) could run in O(1) on certain inputs. An algorithm that is O(n²) could also be very fast on certain inputs. All we know is the worst case is bounded. So an O(n log n) algorithm beats some O(n²) algorithms on some inputs, but not necessarily all of them on all inputs.
How it works
Given two positive integers a and b with a ≥ b:
Compute r = a mod b.
If r = 0, GCD = b. Stop.
Otherwise, set a = b, b = r, and repeat.
Each iteration replaces the larger number with the remainder of dividing by the smaller. The algorithm terminates because the remainder strictly decreases each step.
Counting iterations for the worksheet problem
The question asks which pair requires the most iterations:
(800, 300): 800 → 200 → 100 → 0. Three iterations. GCD = 100.
(100, 55): 100 → 45 → 10 → 5 → 0. Four iterations. GCD = 5.
(29, 18): 29 → 11 → 7 → 4 → 3 → 1 → 0. Six iterations. GCD = 1.
(1000, 999): 1000 → 1 → 0. Two iterations. GCD = 1.
(19, 11): 19 → 8 → 3 → 2 → 1 → 0. Five iterations. GCD = 1.
The answer is (29, 18) with six iterations.
Why some pairs take more iterations
Euclid's algorithm takes the most iterations when the ratio a/b is close to 1 and the numbers do not share a large common factor. Consecutive Fibonacci numbers are the classic worst case: each step reduces the pair by only a small amount. The pair (29, 18) behaves similarly, each remainder is close to the previous one.
By contrast, (1000, 999) looks large, but 1000 mod 999 = 1, so it finishes in two steps. Large numbers do not mean many iterations; the ratio matters more than the magnitude.
Treating Big-O as an exact running time. O(n²) means the running time grows no faster than n², not that it is exactly n². An O(n²) algorithm might run in O(n) on some inputs. Big-O is a ceiling, not a measurement.
Thinking logarithm base matters asymptotically. log₂(n) and log₁₀(n) differ by a constant factor (the change-of-base formula). For asymptotic analysis, the base is irrelevant. Students sometimes write O(log₂ n) as if it is different from O(log n); it is not.
Confusing Big-O with Big-Theta. Saying "merge sort is O(n²)" is technically true but uselessly loose. It is Θ(n log n). Big-O is an upper bound; Big-Theta is a tight bound. Be precise about which claim you are making.
Assuming the limit must exist to apply Big-O. The limit lemmas (Lemmas 4 and 5) apply when the limit exists or is infinite. But f(n) = O(g(n)) can hold even when the limit of f/g does not exist at all. The limit is a sufficient tool, not a necessary one.
⚠️ Be comfortable proving Big-O/Ω/Θ relationships both by finding explicit c and n₀ values and by using the limit. Exam questions may specify which method to use.
⚠️ The change-of-base fact (all log bases are equivalent asymptotically) appears frequently in exam questions designed to test whether you understand what constants do and do not matter.
⚠️ Understand that Big-O describes worst-case growth, not actual performance on a specific input. The "comparing running times" question from the worksheet is a common exam trap.
⚠️ Euclid's algorithm is often used as a warm-up for more complex algorithm analysis. Be able to trace through it by hand and count iterations.
True or false: f(n) = O(g(n)) means f(n) ≤ g(n) for all n. (False. It means f(n) ≤ c · g(n) for all n ≥ n₀, for some constants c and n₀.)
Fill in the blank: If lim(n→∞) f(n)/g(n) = 5, then f(n) = ____(g(n)). (Θ(g(n)), since the limit is finite and positive.)
True or false: 3ⁿ = O(2ⁿ). (False. lim(n→∞) 3ⁿ/2ⁿ = lim (3/2)ⁿ = ∞, which is not finite.)
True or false: GCD(1000, 999) takes more iterations of Euclid's algorithm than GCD(29, 18). (False. (1000, 999) takes 2 iterations; (29, 18) takes 6.)
True or false: If f(n) = O(g(n)) and f(n) = Ω(g(n)), then f(n) = Θ(g(n)). (True. That is the definition of Big-Theta.)
Q: For f(n) = log_a(n) and g(n) = log_b(n) with a, b > 1, is f(n) = O(g(n))? Prove it.
A: Yes. By the change-of-base formula, log_a(n) = log_b(n) / log_b(a). Set c = 1/log_b(a), which is a positive constant, and n₀ = 1. Then log_a(n) = c · log_b(n) ≤ c · log_b(n) for all n ≥ 1. Alternatively, lim(n→∞) log_a(n)/log_b(n) = 1/log_b(a), a finite positive constant, so f = Θ(g).
Q: For f(n) = 4ⁿ and g(n) = 2ⁿ, is f(n) = O(g(n))?
A: No. lim(n→∞) 4ⁿ/2ⁿ = lim(n→∞) 2ⁿ = ∞. The limit is not finite, so by Lemma 4, 4ⁿ ≠ O(2ⁿ). Alternatively, for any constant c, 4ⁿ = (2²)ⁿ = 2²ⁿ, and 2²ⁿ > c · 2ⁿ once n > log₂(c), so no c works.
Q: On the same computer with the same input, an algorithm having O(n log n) worst-case running time runs in less time than all/some/no algorithms having O(n²) worst-case running time. Which is it?
A: "Some." An O(n log n) worst-case bound and an O(n²) worst-case bound say nothing definitive about performance on any specific input. The O(n log n) algorithm could be faster than some O(n²) algorithms for large n, but Big-O is an upper bound: the actual time could be much less. We cannot say "all" because both bounds are ceilings, not exact values.
Q: Which pair of numbers requires the most iterations of Euclid's algorithm: (800, 300), (100, 55), (29, 18), (1000, 999), (19, 11)?
A: (29, 18). Trace: GCD(29, 18) → GCD(18, 11) → GCD(11, 7) → GCD(7, 4) → GCD(4, 3) → GCD(3, 1) → GCD(1, 0). Six iterations. The runner-up is (19, 11) with five.
Asymptotic notation connects directly to algorithm analysis, which is the next major topic in EECS 376. Every time you prove a running-time bound, you are proving a Big-O (or Θ) statement, using exactly the proof techniques from Part 1 of these notes. Euclid's algorithm also reappears in number theory and cryptography (RSA key generation relies on GCD computations). The distinction between upper, lower, and tight bounds becomes critical when you encounter NP-completeness later in the course, where the question is precisely whether a tighter bound exists.
Big-O, Big-Omega, Big-Theta, asymptotic notation, asymptotic analysis, upper bound, lower bound, tight bound, growth rate, order of growth, limit comparison, limit test Big-O, change of base logarithm, log base doesn't matter, 4^n vs 2^n, exponential growth comparison, Euclid's algorithm, Euclidean algorithm, GCD, greatest common divisor, division algorithm, Fibonacci worst case Euclid, EECS 376, foundations of computer science, UMich, algorithm analysis, running time comparison, O(n log n) vs O(n^2)