§3Exercises
Ten exercises in four layers: three proofs, two designs, three implementations with milestones, and two read-the-code. Proofs and designs are the same in both languages; the implementation exercises come as templates in PythonJava with tests that fail on purpose, and your job is to make every test pass. Try each exercise before you open its solution.
| # | Layer | Topic | Video |
|---|
| 1 | Proof | Big-O witnesses | 2 |
| 2 | Proof | Induction | 4 |
| 3 | Proof | Amortized cost of a dynamic array | 3 |
| 4 | Design | Choose an algorithm for a pair-sum query | 1–2 |
| 5 | Design | Design a loop invariant | 4 |
| 6 | Implement | Count steps of loops, then predict the count | 1 |
| 7 | Implement | Dynamic array with a growth policy and a copy counter | 3 |
| 8 | Implement | Fast exponentiation with a checked invariant | 4 |
| 9 | Read the code | An AI claims a loop is linear | 1 |
| 10 | Read the code | An AI claims insert is constant time | 1, 3 |
PROOFS
Exercise 1 · Big-O witnesses. Let f(n) = 3n² + 10n + 5. (a) Prove f(n) = O(n²) by giving explicit constants c and n₀ and checking the inequality for every n ≥ n₀. (b) Prove f(n) = Ω(n²). What do (a) and (b) together say about f? (c) Prove that n² is not O(n). (Suppose it is, and derive a contradiction.) (d) Is 2^(n+1) = O(2ⁿ)? Is 2^(2n) = O(2ⁿ)? Prove both answers.
Solution
Definitions (video 2): f(n) = O(g(n)) means there are constants c > 0 and n₀ such that f(n) ≤ c·g(n) for every n ≥ n₀; f(n) = Ω(g(n)) means f(n) ≥ c·g(n) for every n ≥ n₀; Θ means both.
(a) Take c = 5 and n₀ = 10. For every n ≥ 10 we have 10n ≤ n² (divide by n > 0: 10 ≤ n) and 5 ≤ n², so f(n) = 3n² + 10n + 5 ≤ 3n² + n² + n² = 5n². (Other witnesses work too, for example c = 18 and n₀ = 1: for n ≥ 1, 10n ≤ 10n² and 5 ≤ 5n², so f(n) ≤ 18n². Any valid pair is a correct answer; a pair is only "wrong" if the inequality fails for some n ≥ n₀. For instance c = 4 fails at n = 1 because f(1) = 18 > 4.)
(b) Take c = 3 and n₀ = 1. All three terms are non-negative, so f(n) ≥ 3n² for every n ≥ 1. Hence f(n) = Ω(n²). With (a), f(n) = Θ(n²): f grows exactly as fast as n², up to constant factors.
(c) Suppose n² = O(n): there are c > 0 and n₀ with n² ≤ c·n for all n ≥ n₀. Dividing by n > 0 gives n ≤ c for all n ≥ n₀. But n = max(n₀, ⌈c⌉ + 1) is at least n₀ and larger than c, a contradiction.
(d) 2^(n+1) = 2·2ⁿ, so c = 2 and n₀ = 0 give 2^(n+1) = O(2ⁿ): yes. 2^(2n) = (2ⁿ)². Suppose (2ⁿ)² ≤ c·2ⁿ for all n ≥ n₀. Dividing by 2ⁿ gives 2ⁿ ≤ c. By Exercise 2(c), 2ⁿ ≥ n + 1, so for n = max(n₀, ⌈c⌉) we get 2ⁿ ≥ n + 1 > c, a contradiction. So 2^(2n) is not O(2ⁿ): a constant in the exponent is not a constant factor.
Exercise 2 · Induction. (a) Prove by induction that for every k ≥ 0: 1 + 2 + 4 + … + 2ᵏ = 2^(k+1) − 1. (b) A dynamic array doubles its capacity from 1 to 2, 4, …, 2ᵏ, copying every stored element at each resize. Use (a) to compute the total number of elements copied. (c) Prove by induction that 2ⁿ ≥ n + 1 for every n ≥ 0. What does this say about log₂(n + 1)?
Solution
(a) Claim P(k): Σᵢ₌₀ᵏ 2ⁱ = 2^(k+1) − 1. Base k = 0: the sum is 2⁰ = 1 and 2¹ − 1 = 1. ✓ Step: assume P(k). Then Σᵢ₌₀^(k+1) 2ⁱ = (Σᵢ₌₀ᵏ 2ⁱ) + 2^(k+1) = (2^(k+1) − 1) + 2^(k+1) = 2·2^(k+1) − 1 = 2^(k+2) − 1, which is P(k+1). By induction P(k) holds for all k ≥ 0. ∎
(b) Going from capacity 2ʲ to 2^(j+1) copies 2ʲ elements (the array is full). Starting at capacity 1 = 2⁰ and ending at 2ᵏ, the resizes are j = 0, …, k − 1, so the total is Σⱼ₌₀^(k−1) 2ʲ = 2ᵏ − 1 by (a) with k − 1 (for k = 0 there is no resize and 2⁰ − 1 = 0 ✓). So the total copying is one less than the final capacity: if the final capacity is n = 2ᵏ, fewer than n copies in total.
(c) Claim: 2ⁿ ≥ n + 1. Base n = 0: 1 ≥ 1. ✓ Step: assume 2ⁿ ≥ n + 1. Then 2^(n+1) = 2·2ⁿ ≥ 2(n + 1) = 2n + 2 ≥ n + 2, because n ≥ 0. ∎ Taking log₂ of both sides: n ≥ log₂(n + 1), i.e. the logarithm grows more slowly than n (it is what lets us say log n = O(n)).
Exercise 3 · Amortized cost. A dynamic array starts with capacity 1 and size 0. An append into a full array (size = capacity) first doubles the capacity and copies every element; then it writes the new element. Cost model: 1 per element written by an append, 1 per element copied. (a) Aggregate: prove that n appends cost less than 3n in total. (b) Accounting: charge 3 coins per append. Explain what each coin pays for and prove the account never goes negative. (c) Now grow by 1 instead of doubling (capacity → capacity + 1 when full). Compute the total cost of n appends exactly, and the amortized cost per append in Θ-notation.
Solution
Set-up: appends are numbered 1, 2, …, n. Append i happens when the size is i − 1.
(a) The array is full exactly when the size equals the capacity. Capacity starts at 1 and doubles at each resize, so the capacity is always the smallest power of two that is at least the size (1 for sizes 0 and 1), and append i finds the array full exactly when i − 1 is a power of two, i − 1 = 2ʲ (append 2 with j = 0, append 3 with j = 1, append 5 with j = 2, …). That resize copies 2ʲ elements. For n ≥ 2 let J = ⌊log₂(n − 1)⌋, so 2ᴶ ≤ n − 1. The resizes among the first n appends are j = 0, …, J, and total copies = Σⱼ₌₀ᴶ 2ʲ = 2^(J+1) − 1 ≤ 2(n − 1) − 1 < 2n (by Exercise 2(a)). For n = 1 there are 0 copies. Writes cost n. Total cost = n + copies < n + 2n = 3n, so each append costs less than 3 on average over the sequence. ∎
(b) Charge 3 coins per append. One coin pays for writing the new element; the other two are stored on the new element. A resize at size m copies m elements and costs m. Claim: just before a resize at size m, the elements appended since the previous resize hold at least m unspent coins, enough to pay for it. For m = 1 (the first resize) the single element holds 2 ≥ 1 coins. For m ≥ 2 the previous resize happened at size m/2, so exactly m/2 elements have been appended since then, holding 2·(m/2) = m coins. Spending them leaves no coins on older elements (or only leftovers, which can only help). So the balance never goes negative, the real cost is at most the total charge 3n, and the amortized cost per append is O(1) (at most 3). ∎
(c) With growth by 1 the capacity always equals the size right after a resize, so every append i ≥ 2 finds the array full and copies i − 1 elements. Total copies = Σᵢ₌₂ⁿ (i − 1) = n(n − 1)/2. Total cost = n + n(n − 1)/2 = n(n + 1)/2, so the amortized cost per append is (n + 1)/2 = Θ(n), against O(1) for doubling. Growing by any constant amount k has the same problem (a resize every k appends, each copying a number of elements proportional to n); only multiplying the capacity by a constant factor greater than 1 gives O(1) amortized.
DESIGNS
Exercise 4 · Pair sum. Given n integers and a target T, decide whether two different positions hold values that add up to T. Design three solutions: (A) check all pairs; (B) sort, then walk two pointers inward from both ends; (C) one pass with a hash set. For each give the running time as a function of n (state what you assume about sorting and hashing), the extra space, and one situation in which you would pick it. What does each cost for n = 1,000,000 (count steps, as in video 1)?
Solution
Assume a comparison sort in O(n log n) and a hash set with O(1) expected time per lookup and insert (chapter 7).
| Time | Extra space | Pick it when |
|---|
| A all pairs | n(n−1)/2 = O(n²) | O(1) | n is tiny, or memory is very tight and the input must not be reordered |
| B sort + two pointers | O(n log n) sort + ≤ n−1 pointer steps = O(n log n) | O(1) if sorted in place (reorders the input), O(n) for a copy | the data is already sorted (then O(n)), or hashing is not available / not trustworthy |
| C hash set | O(n) expected | O(n) | general case, large n, memory is available |
Two pointers: i = 0, j = n − 1; while i < j: s = a[i] + a[j]; if s = T return found; if s < T then i++ else j−−. It is correct because if s < T then a[i] + a[k] ≤ s < T for every k ≤ j, so a[i] cannot be part of any answer among the remaining items and can be dropped; the case s > T is symmetric. Hash set: for each x in order, if T − x is already in the set return found, then add x. Checking before adding makes the two positions different (a value pairs with itself only if it occurs twice). Counts for n = 1,000,000: A ≈ 5·10¹¹ comparisons (the number from video 1); B ≈ n·log₂ n ≈ 2·10⁷ comparisons to sort plus at most 10⁶ pointer steps; C ≈ 10⁶ lookups and 10⁶ inserts. The caveat for C is that "expected O(1)" depends on the hash function; a bad one degrades toward O(n²).
Exercise 5 · Loop invariant. Fast exponentiation computes xⁿ (n ≥ 0 an integer) like this:
Solution
Invariant: at the top of every iteration (every time the loop condition is evaluated), result · baseᵉ = xⁿ (with the convention b⁰ = 1, also for b = 0).
Initialization. Before the first iteration result = 1, base = x, e = n, so result · baseᵉ = 1 · xⁿ = xⁿ. ✓ Maintenance. Assume the invariant and e > 0 at the top of an iteration. Let result′, base′, e′ be the values at the top of the next one. If e is even: result′ = result, base′ = base², e′ = e/2, so result′ · base′^(e′) = result · (base²)^(e/2) = result · baseᵉ = xⁿ. ✓ If e is odd: result′ = result · base, base′ = base², e′ = (e − 1)/2, so result′ · base′^(e′) = result · base · base^(e−1) = result · baseᵉ = xⁿ. ✓ Termination. While e > 0, e′ = ⌊e/2⌋ < e and e′ ≥ 0 is an integer, so e strictly decreases and reaches 0 after finitely many iterations. When the loop exits, e = 0, so the invariant says result · base⁰ = result = xⁿ. The returned value is xⁿ. ∎ Cost. e is halved (rounded down) each time, so the loop runs ⌊log₂ n⌋ + 1 times for n ≥ 1 (the bit length of n) and 0 times for n = 0. Each iteration does one squaring and at most one more multiplication, so there are at most 2(⌊log₂ n⌋ + 1) = O(log n) multiplications, against n − 1 for the naive loop.
result = 1; base = x; e = nwhile e > 0: if e is odd: result = result * base base = base * base e = e // 2return result
Design the loop invariant (one equation relating result, base, e, x and n). Prove initialization, maintenance (treat e even and e odd separately) and termination, and conclude that the returned value is xⁿ. Then count the iterations and the multiplications as a function of n.
IMPLEMENTATIONS (WITH MILESTONES)
Each file lists its milestones at the top. Do them in order and run the tests after each one.
Exercise 6 · Count the steps — ex_steps.pyExSteps.java. Write the loops and count their iterations, then write the closed form your analysis predicts and let the tests check that they agree. Includes a loop whose variable halves (count = ⌊log₂ n⌋) and a triple loop with i ≤ j ≤ k.
Solution
Closed forms (the tests check them against the loops):
count_pairs(n) = n(n−1)/2. Row i of the double loop has n − 1 − i iterations; (n−1) + (n−2) + … + 0 = n(n−1)/2.count_halving(n) = ⌊log₂ n⌋ for n ≥ 1. If 2ᵏ ≤ n < 2^(k+1) then k halvings bring n to 1 and not before. In Python n.bit_length() - 1; in Java 31 - Integer.numberOfLeadingZeros(n). Avoid math.log2/Math.log: floating point can round a boundary such as 2^k − 1 the wrong way.count_triple(n) = n(n+1)(n+2)/6, the number of triples i ≤ j ≤ k < n (that is C(n+2, 3)). Summing over i: for each (i, j) the innermost loop runs n − j times; the pair count with a given i is Σⱼ₌ᵢⁿ⁻¹ (n − j) = T(n − i) with T(m) = m(m+1)/2, and Σₘ₌₁ⁿ m(m+1)/2 = n(n+1)(n+2)/6. Check n = 3: 10.- Java: use
long. n * (n - 1) is computed in int and overflows for n = 1,000,000 unless you cast first: (long) n * (n - 1) / 2.
Exercise 7 · Growth policies — ex_dynarray.pyExDynArray.java. Implement append with a pluggable growth policy and a copy counter, then the two policies double and plus_one. The tests check the capacities, the exact copy counts and the bounds you proved in Exercise 3.
Solution
Reference implementation in solutions/. The numbers the tests encode, all from Exercise 3: with doubling, resizes happen at append 2ʲ + 1 and copy 2ʲ elements, so n appends make 2^(J+1) − 1 copies with J = ⌊log₂(n − 1)⌋ (1025 appends: 2¹¹ − 1 = 2047 copies, less than 2n = 2050), and (n + copies)/n < 3. With +1, copies = n(n − 1)/2. The point of the exercise: the only difference is one line of the policy.
Exercise 8 · Checked invariant — ex_power.pyExPower.java. Implement fast exponentiation so that the invariant from Exercise 5 holds at every call of the hook; the tests check it, and check that the number of iterations is logarithmic.
Solution
Reference implementation in solutions/: the loop is exactly the pseudocode of Exercise 5, with the hook called at the top of every iteration and once more when the condition fails (e = 0). The hook is called ⌊log₂ n⌋ + 2 times for n ≥ 1 and once for n = 0, i.e. n.bit_length() + 1 times — the test for "logarithmic".
READ THE CODE
An AI assistant wrote each function and a complexity claim for it. The code is correct; the claim is wrong. Find the error, state the real complexity (best and worst case where they differ), and say how to fix it. Use the three-step habit from the chapter: look for hidden loops, count, double n.
Exercise 9 — has_duplicate in read/py/ex_read.py / hasDuplicate in read/java/ExRead.java.
Solution
The error: the claim counts the visible loop and forgets the hidden one. x in seen on a list scans the list, comparing with each stored item until it finds x, so every test costs up to len(seen) comparisons. On n distinct items the i-th test makes i − 1 comparisons, in total 0 + 1 + … + (n − 1) = n(n − 1)/2: Θ(n²) in the worst case (the same count as the all-pairs version; the test in solutions/ confirms exactly n(n−1)/2 comparisons). Best case O(1): a duplicate among the first two items. Java: ArrayList.contains scans using equals, same analysis. Fix: seen = set() (Java HashSet<T>): membership and insertion are O(1) expected, so the function is O(n) expected. The claim "exactly like the set-based version" was the giveaway: it is not, and the only difference is the type of seen.
Exercise 10 — reversed_copy in read/py/ex_read.py / reversedCopy in read/java/ExRead.java.
Solution
The error: list.insert(0, x) is not constant time. Python lists (and ArrayList) store their elements in one contiguous array; inserting at the front moves every element already stored one place to the right (the ArrayList.add(index, e) documentation says so explicitly). When the i-th element is inserted there are i − 1 elements to move, in total n(n − 1)/2 moves: Θ(n²). The doubling test exposes it: ten times more input is about a hundred times more work. Fix: list(reversed(items)), or append everything and reverse once (O(n)); if you really need cheap insertion at the front use collections.deque.appendleft (Java: ArrayDeque.addFirst), O(1) each. Note what the claim got right: the result is correct and "one loop" is true; the claim was wrong because the body of that loop is not O(1).