Source: EECS 376 Homework 1 (Problems 2 and 5)
Tags: big-O, asymptotic analysis, growth rates, limit argument, L'Hopital's rule, EECS 376, foundations of computer science, algorithm complexity
Difficulty: Introductory to Intermediate
Prerequisites: Basic calculus (limits, L'Hopital's Rule), logarithm properties, exponent rules.
Asymptotic notation is the language computer scientists use to talk about how algorithms scale. Rather than counting exact operations, you classify a function's long-run growth relative to another function. This is foundational to everything that follows in EECS 376: once you can reason about whether one function dominates another, you can compare algorithms, prove lower bounds, and analyse complexity classes. You should already be comfortable with basic limit evaluation and logarithm identities before diving in.
Big-O notation captures an upper bound on how fast a function grows. To check whether f(n) = O(g(n)), you either find constants c and n0 that make f(n) <= c * g(n) for all n >= n0, or you show the limit of f(n)/g(n) is finite. The five sub-problems in HW1 P2 walk through the main comparison families: polynomial vs polynomial, polynomial vs exponential, exponential vs exponential, and logarithmic variants.
Big-O notation, O(g(n))
We say f(n) = O(g(n)) if there exist positive constants c and n0 such that f(n) <= c * g(n) for all n >= n0. In simple terms, this means f grows no faster than g, up to a constant factor, once n is large enough.
Limit test for Big-O
If lim (n -> infinity) f(n)/g(n) = L, where L is a finite non-negative number, then f(n) = O(g(n)). If the limit is infinity, then f(n) is not O(g(n)). Think of it as: if the ratio settles to a finite value, f does not outgrow g.
L'Hopital's Rule
When lim f(n)/g(n) yields an indeterminate form (0/0 or infinity/infinity), you may take the derivative of the numerator and denominator separately and evaluate the new limit. In simple terms, it is a calculus shortcut for resolving stubborn limit comparisons.
Asymptotic growth rate
The rate at which a function increases as its input grows without bound, ignoring constant factors and lower-order terms. Think of it as the "shape" of the curve when you zoom out far enough that only the dominant term matters.
Polynomial growth
Functions of the form n^k for some constant k. These grow faster than any logarithmic function but slower than any exponential function.
Exponential growth
Functions of the form a^n for some constant a > 1. These eventually outpace any polynomial, no matter how large the polynomial's degree.
Definition method: Find explicit constants c and n0 such that f(n) <= c * g(n) for all n >= n0. This is the ground-truth approach and works well when the relationship is straightforward.
Limit method: Compute lim (n -> infinity) f(n)/g(n). If the limit is a finite non-negative number, then f(n) = O(g(n)). If the limit is infinity, f(n) is not O(g(n)). If the limit is 0, then f(n) = O(g(n)) and additionally g(n) is not O(f(n)).
Part (a): f(n) = n + 2 log2(n) + 3, g(n) = (1/3)n + 2
Answer: Yes, f(n) = O(g(n)).
Reasoning: Both f and g are dominated by their linear terms. Using the limit test:
lim (n -> inf) [n + 2 log2(n) + 3] / [(1/3)n + 2] = lim [n] / [(1/3)n] = 3
The limit is finite (equal to 3), so f(n) = O(g(n)). Alternatively, for n >= 1, we have n + 2 log2(n) + 3 <= n + 2n + 3n = 6n <= 18 * ((1/3)n + 2), so c = 18, n0 = 1 works.
Part (b): f(n) = n^2, g(n) = 2^n
Answer: Yes, f(n) = O(g(n)).
Reasoning: Polynomials always grow slower than exponentials. Using the limit test:
lim (n -> inf) n^2 / 2^n
Apply L'Hopital's Rule twice (both numerator and denominator go to infinity):
First application: lim 2n / (2^n * ln 2)
Second application: lim 2 / (2^n * (ln 2)^2) = 0
The limit is 0, which is finite, so f(n) = O(g(n)).
Part (c): f(n) = 3^n, g(n) = 2^n
Answer: No, f(n) is not O(g(n)).
Reasoning: lim (n -> inf) 3^n / 2^n = lim (3/2)^n = infinity.
Since 3/2 > 1, the ratio grows without bound. A larger-base exponential always dominates a smaller-base exponential.
Part (d): f(n) = ln(n), g(n) = ln(n/5)
Answer: Yes, f(n) = O(g(n)).
Reasoning: Note that ln(n/5) = ln(n) - ln(5). So:
lim (n -> inf) ln(n) / [ln(n) - ln(5)] = lim 1 / [1 - ln(5)/ln(n)] = 1
The limit is 1 (finite), so f(n) = O(g(n)). The constant offset ln(5) becomes negligible as n grows.
Part (e): f(n) = (log2 n)^3, g(n) = 2^(log2 n) = n
Answer: Yes, f(n) = O(g(n)).
Reasoning: Note that g(n) = 2^(log2 n) = n. So the question is whether (log2 n)^3 = O(n). Any power of a logarithm grows slower than any positive power of n. Using the limit test:
lim (n -> inf) (log2 n)^3 / n = 0
You can verify this by substituting m = log2 n (so n = 2^m) and evaluating lim m^3 / 2^m = 0 (apply L'Hopital's Rule three times). The limit is 0, so f(n) = O(g(n)).
Big-O definition:
f(n) = O(g(n)) iff there exist c > 0 and n0 >= 1 such that f(n) <= c * g(n) for all n >= n0.
Limit test:
If lim (n -> infinity) f(n)/g(n) = L where 0 <= L < infinity, then f(n) = O(g(n)).
If lim (n -> infinity) f(n)/g(n) = infinity, then f(n) is not O(g(n)).
Growth hierarchy (slowest to fastest):
1 < log n < (log n)^k < n^epsilon < n < n log n < n^2 < n^k < 2^n < 3^n < n! < n^n
(where k > 2, epsilon > 0)
Useful logarithm identities:
log(a * b) = log a + log b
log(a / b) = log a - log b
log(a^k) = k * log a
2^(log2 n) = n
Change of base: log_a(n) = log_b(n) / log_b(a)
Asymptotic analysis is how engineers decide whether an algorithm will scale. When a database query runs in O(n log n) versus O(n^2), that difference determines whether the system handles a million records in seconds or hours. Every time you hear "this algorithm is linear" or "this search is logarithmic," someone has done exactly this kind of Big-O reasoning.
Students often think Big-O gives an exact running time. It does not. It gives an upper bound on the growth rate, ignoring constants and lower-order terms.
Students sometimes assume f(n) = O(g(n)) means f and g grow at the same rate. That is wrong. f(n) = O(g(n)) only says f grows no faster than g. For example, n = O(n^2) is true, but n and n^2 do not grow at the same rate.
A common error is forgetting that log bases do not matter in Big-O. Since log_a(n) = log_b(n) / log_b(a), different bases differ only by a constant factor, so O(log2 n) = O(ln n) = O(log n).
Students sometimes apply L'Hopital's Rule when the limit is not actually indeterminate. Check that you have 0/0 or infinity/infinity before differentiating.
The homework gives this pseudocode:
function SOLVE-HW(X):
for i in range(sqrt(X)):
print 'hey grader, give me ' + X + ' points '
return XThe question asks for an asymptotic bound on the total number of characters printed.
Breaking it down:
The loop runs sqrt(X) times.
Each iteration prints a fixed string plus the decimal representation of X.
The decimal representation of X has floor(log10(X)) + 1 characters, which is Theta(log X).
The fixed string "hey grader, give me ... points" has a constant number of characters plus the digits of X, so each print statement outputs Theta(log X) characters.
Total characters = sqrt(X) iterations * Theta(log X) characters per iteration = Theta(sqrt(X) * log X).
The tight asymptotic bound is Theta(sqrt(X) * log X).
⚠️ You must be able to apply both the definition method and the limit method. Exam questions may specify which one to use.
⚠️ Know the growth hierarchy cold: logarithmic < polynomial < exponential. Most comparison questions reduce to placing both functions in this hierarchy.
⚠️ When using L'Hopital's Rule, you may need to apply it more than once (as in the n^2 vs 2^n comparison). Each application reduces the polynomial degree by one.
⚠️ Watch for disguised functions. 2^(log2 n) = n is a classic trick. Simplify before comparing.
⚠️ For program analysis questions, separately count the number of loop iterations and the cost per iteration. Multiply them for the total.
True or false: If f(n) = O(g(n)), then g(n) = O(f(n)). _____
True or false: O(log2 n) and O(ln n) describe the same set of functions. _____
Fill in the blank: lim (n -> inf) n^3 / 2^n = _____
True or false: 3^n = O(2^n). _____
Fill in the blank: The number of digits in the decimal representation of X is Theta(_____).
Q: Is n^2 + 5n + 100 = O(n^2)? Justify using the definition.
A: Yes. For n >= 10, we have 5n <= n^2 and 100 <= n^2, so n^2 + 5n + 100 <= 3n^2. Choose c = 3, n0 = 10.
Q: Is 2^(n+1) = O(2^n)?
A: Yes. 2^(n+1) = 2 * 2^n, so choose c = 2, n0 = 1.
Q: Using the limit test, determine whether n * log n = O(n^2).
A: lim (n -> inf) (n log n) / n^2 = lim (log n) / n = 0. The limit is 0 (finite), so yes, n log n = O(n^2).
Q: A loop runs n times and each iteration does O(log n) work. What is the total complexity?
A: O(n log n). Multiply the number of iterations by the per-iteration cost.
Q: Why does the limit test fail to distinguish between f(n) = 3n and g(n) = 5n for Big-O purposes?
A: lim 3n/5n = 3/5, which is finite, so f = O(g). Also lim 5n/3n = 5/3, which is also finite, so g = O(f). Both are true because they differ only by a constant factor. Big-O ignores constant factors.
Big-O is the gateway to complexity theory, which is the central theme of EECS 376. Once you are comfortable with asymptotic comparisons, you will use them to classify problems into complexity classes (P, NP) and to analyse the running time of specific algorithms like the Euclidean algorithm (also in this homework). The limit techniques here also connect to the analysis of recurrences (Master Theorem) that you will see in later assignments.
asymptotic notation, Big-O, Big-Omega, Big-Theta, growth rate, order of growth, limit comparison, L'Hopital's Rule, polynomial time, exponential time, logarithmic growth, algorithm analysis, EECS 376, computational complexity, upper bound, dominance relation, rate of growth