Difficulty: Introductory to Intermediate | Prerequisites: Comfort with limits, logarithms, and basic algebra. Familiarity with summation notation helps.
Asymptotic notation is how computer scientists talk about how fast algorithms grow as inputs get large. Rather than pinning down exact running times (which depend on hardware, language, compiler), we classify functions by their growth rate. This homework also introduces binary representation, which is the foundation of how computers encode information. These concepts underpin every later topic in EECS 376, from complexity classes to information theory.
Big-O, Big-Theta, and little-o describe how functions compare as n grows. Big-O is an upper bound, Big-Theta means the same growth rate, and little-o means strictly slower growth. A program whose running time does not depend on its input runs in O(1). To represent n items with binary strings, you need at least ceil(log_2(n)) bits.
Big-O notation, O(g(n))
f(n) = O(g(n)) means there exist constants M > 0 and n_0 such that for all n >= n_0, f(n) <= M * g(n). In other words, f grows no faster than g, up to a constant factor, once n is large enough.
Think of it as an upper bound on growth rate. "f is at most on the order of g."
Big-Theta notation, Theta(g(n))
f(n) = Theta(g(n)) means f(n) = O(g(n)) and g(n) = O(f(n)). The two functions grow at the same rate, within constant factors.
Think of it as: f and g are in the same growth-rate class.
Little-o notation, o(g(n))
f(n) = o(g(n)) means that for every constant M > 0, there exists n_0 such that for all n >= n_0, f(n) <= M * g(n). Equivalently, lim_{n->inf} f(n)/g(n) = 0. This is a strict bound: f grows strictly slower than g.
Think of it as: f becomes negligible compared to g.
O(1), constant time
A function or algorithm that runs in O(1) time takes a fixed amount of work regardless of the input size. The actual time may vary by hardware, but it does not depend on n.
Binary string of length k
A sequence of k symbols, each 0 or 1. There are exactly 2^k distinct binary strings of length k.
Ceiling function, ceil(x)
The smallest integer greater than or equal to x. Written as ceil(x) or with the bracket notation. Used to round up when a non-integer result must be promoted to a whole number (e.g. the number of bits needed).
Answer: No.
f(n) = Theta(n) because n/2 + 4 grows linearly.
g(n) = Theta(sqrt(n)) because the sqrt(n) term dominates the log term.
Since sqrt(n) = o(n), meaning sqrt(n) grows strictly slower than n, we have g(n) = o(f(n)). So f(n) cannot be O(g(n)).
Technique used: show the two functions live in different growth classes (Theta(n) vs Theta(sqrt(n))), then use the fact that a slower-growing function cannot upper-bound a faster one.
Answer: Yes.
g(n) = n^3/27, so f(n) = n^3 = 27 * g(n).
Setting M = 27 and n_0 = 1, we have f(n) <= 27 * g(n) for all n >= 1. This satisfies the Big-O definition directly.
Technique used: find an explicit constant M that makes the inequality work. When two functions differ only by a constant factor, each is O of the other.
Answer: Yes (and in fact f(n) = o(g(n))).
Apply L'Hopital's Rule to lim_{n->inf} n^2 / 2^n.
First application: lim 2n / (2^n * ln(2)).
Second application: lim 2 / (4^n * (ln(2))^2) = 0.
Since the limit is 0, f(n) = o(g(n)), which is stronger than O.
Technique used: L'Hopital's Rule to evaluate the limit of the ratio. A limit of 0 proves little-o (and therefore Big-O).
Answer: No.
lim_{n->inf} g(n)/f(n) = lim 2^{n/2} / 2^n = lim 1/2^{n/2} = 0.
So g(n) = o(f(n)), meaning g grows strictly slower than f. Therefore f(n) cannot be O(g(n)).
Answer: Yes.
Take c = 5 and solve for when n * ln(n) <= 5 * n * ln(n/5).
Algebraic manipulation using properties of logarithms gives x >= 8.
So for all n >= 8, f(n) <= 5 * g(n), satisfying the Big-O definition with M = 5 and n_0 = 8.
Technique used: pick a candidate constant, then solve the resulting inequality to find n_0.
The program prints a fixed statement regardless of what input it receives. Because the work done does not depend on the size of the input, the running time is O(1), or "constant time."
The actual wall-clock time may vary depending on hardware, operating system, or the cost of the print operation. But as a function of the input size n, the time is a constant: it does not grow with n. That is what O(1) means.
When the code does not read or iterate over the input.
When the number of operations is bounded by a fixed constant, no matter how large the input.
Array access by index, hash table lookup (amortised), and returning a precomputed value are common O(1) operations.
The question: find the smallest k such that k-bit binary strings can uniquely represent n distinct elements.
Key facts:
A binary string of length k has exactly 2^k possible values (each of the k positions is independently 0 or 1).
For k = 0, there is exactly one string: the empty string.
To represent n elements, we need 2^k >= n.
The answer: k = ceil(log_2(n)).
Why the ceiling? log_2(n) is often not an integer. For example, log_2(5) is roughly 2.32. You cannot have 2.32 bits, so you round up to 3 bits. With 3 bits you get 2^3 = 8 possible strings, which is enough for 5 elements.
Edge cases to keep in mind:
If n is a power of 2, log_2(n) is already an integer and no rounding is needed.
If n = 1, you need k = 0 bits (the empty string suffices, though in practice one bit is often used).
If n = 0, the question is vacuous.
Big-O definition:
f(n) = O(g(n)) iff there exist M > 0 and n_0 such that f(n) <= M * g(n) for all n >= n_0.
Big-Theta definition:
f(n) = Theta(g(n)) iff f(n) = O(g(n)) and g(n) = O(f(n)).
Little-o definition:
f(n) = o(g(n)) iff for every M > 0, there exists n_0 such that f(n) <= M * g(n) for all n >= n_0. Equivalently, lim_{n->inf} f(n)/g(n) = 0.
Little-o implies Big-O:
If f(n) = o(g(n)), then f(n) = O(g(n)). The converse is false.
Growth rate hierarchy (slowest to fastest):
1 < log(n) < sqrt(n) < n < n * log(n) < n^2 < n^3 < 2^n < n! < n^n
Binary strings:
Number of distinct strings of length k = 2^k. Minimum bits to represent n elements: k = ceil(log_2(n)).
Asymptotic notation is how engineers decide whether an algorithm is practical at scale. An O(n^2) sorting algorithm might be fine for 100 items but unusable for 10 million. Binary representation and the ceil(log_2(n)) formula show up every time you design a data format, a network protocol, or an addressing scheme: IP addresses use 32 bits (IPv4) or 128 bits (IPv6) precisely because of this relationship between the number of bits and the number of things you can name.
Students often treat Big-O as an exact characterisation. It is only an upper bound. Saying f(n) = O(n^2) does not mean f grows quadratically; it means f grows no faster than quadratically. f could be linear or even constant.
Students confuse Big-O with Big-Theta. "This algorithm is O(n^2)" is weaker than "this algorithm is Theta(n^2)." The first says it is at most quadratic; the second says it is exactly quadratic.
Students sometimes think little-o and Big-O are interchangeable. They are not. Little-o is strictly stronger: f(n) = o(g(n)) means f is negligible compared to g, not just bounded by it.
When computing minimum bits, students sometimes forget the ceiling and write k = log_2(n) even when log_2(n) is not an integer. You cannot have a fractional number of bits.
⚠️ You will be asked to prove or disprove Big-O relationships on exams. The standard techniques are: find explicit M and n_0, use L'Hopital's Rule to evaluate a limit, or show that one function is Theta of a different growth class.
⚠️ Know the growth-rate hierarchy cold (log < sqrt < linear < n log n < polynomial < exponential < factorial). Many exam questions reduce to placing two functions in this hierarchy.
⚠️ Little-o implies Big-O but not vice versa. This distinction is commonly tested.
⚠️ "Constant time" means O(1) as a function of n, not that the operation is fast. Printing a million-character string is O(1) if the string is fixed and does not depend on the input.
True or false: if f(n) = O(g(n)), then g(n) = O(f(n)). Answer: False. Big-O is not symmetric. f might grow slower than g.
Fill in the blank: the number of distinct binary strings of length 5 is ___. Answer: 32 (2^5).
True or false: n^2 = o(2^n). Answer: True. Polynomial growth is always little-o of exponential growth.
Fill in the blank: to uniquely represent 1000 items with binary strings, you need at least ___ bits. Answer: 10 (since ceil(log_2(1000)) = 10, because 2^10 = 1024 >= 1000).
True or false: a program that always prints "hello" regardless of input runs in O(n) time. Answer: True (O(1) is a subset of O(n)), but O(1) is the tighter and more informative bound.
Q: Prove that 3n + 7 = O(n). State the constants M and n_0 explicitly.
A: Choose M = 4 and n_0 = 7. For all n >= 7, 3n + 7 <= 3n + n = 4n = M * n. Therefore 3n + 7 = O(n).
Q: Is 2^n = O(n^100)? Why or why not?
A: No. Exponential functions grow faster than any polynomial. By L'Hopital's Rule (applied 100 times), lim_{n->inf} n^100 / 2^n = 0, so n^100 = o(2^n), which means 2^n is not O(n^100).
Q: A program reads an input of size n but only looks at the first 10 elements. What is its time complexity?
A: O(1), because the work done (looking at 10 elements) is bounded by a constant regardless of n. Reading the input itself may take O(n) depending on the model, but the computation on it is O(1).
Q: You need to assign unique binary codes to 50 students. What is the minimum code length?
A: ceil(log_2(50)) = ceil(5.64) = 6 bits. With 6 bits you can represent 2^6 = 64 distinct codes, which is enough for 50 students.
Q: Give an example of two functions where f(n) = O(g(n)) but f(n) is not Theta(g(n)).
A: f(n) = n and g(n) = n^2. We have n = O(n^2) (choose M = 1, n_0 = 1), but n^2 is not O(n), so f(n) is not Theta(g(n)).
Asymptotic notation is the language you will use to state every complexity result in EECS 376: P, NP, and the classes beyond are all defined in terms of Big-O bounds on running time or space. The binary representation material connects to information theory and coding theory, where the question "how many bits do you need?" is the central concern. L'Hopital's Rule, used to compare growth rates, reappears in the analysis of randomised algorithms and expected running times.
Big-O notation, Big-Theta, Big-Omega, little-o, asymptotic analysis, growth rate, time complexity, constant time, O(1), L'Hopital's Rule, binary representation, binary encoding, minimum bit length, ceiling function, log base 2, polynomial vs exponential, EECS 376, foundations of computer science, University of Michigan, algorithm analysis, worst-case complexity