Method: replace T(n) by its definition k times, find the pattern in k, stop when the argument reaches the base case, then prove the pattern by induction.

(a) T(n) = T(n/2) + 1 = T(n/4) + 2 = T(n/8) + 3 = … = T(n/2ʲ) + j. With n = 2ᵏ and j = k: T(n) = T(1) + k = k + 1 = log₂ n + 1. Proof. Claim P(k): T(2ᵏ) = k + 1. Base k = 0: T(1) = 1. ✓ Step: T(2^(k+1)) = T(2ᵏ) + 1 = k + 2 = (k + 1) + 1. ✓ ∎ Compare with the table of worst-case probes in video 2: n = 1, 2, 4, …, 1024 needs 1, 2, 3, …, 11 probes, i.e. k + 1 for n = 2ᵏ. (The table is the exact worst case of binary search; this recurrence reproduces it because one probe leaves at most half of the items.)

(b) T(n) = 2T(n/2) + n = 4T(n/4) + 2n = 8T(n/8) + 3n = … = 2ʲ·T(n/2ʲ) + j·n. With n = 2ᵏ and j = k: T(n) = n·T(1) + k·n = n log₂ n (T(1) = 0). Proof. P(k): T(2ᵏ) = k·2ᵏ. Base k = 0: T(1) = 0 = 0·1. ✓ Step: T(2^(k+1)) = 2·T(2ᵏ) + 2^(k+1) = 2·k·2ᵏ + 2^(k+1) = (k + 1)·2^(k+1). ✓ ∎ Reading it as a tree: level j has 2ʲ subproblems of size n/2ʲ, each costing n/2ʲ for its merge or partition, so every level costs n, and there are k = log₂ n levels. That is the n log n of merge sort (the measured 8,715 comparisons for n = 1,000 in Python are below n log₂ n ≈ 9,966, because merging stops early when one list runs out).

(c) T(n) = T(n − 1) + (n − 1) = T(n − 2) + (n − 2) + (n − 1) = … = 0 + 1 + 2 + … + (n − 1) = n(n − 1)/2. Proof. P(n): T(n) = n(n − 1)/2. Base n = 0: T(0) = 0. ✓ Step: T(n + 1) = T(n) + n = n(n − 1)/2 + n = n(n + 1)/2 = (n + 1)·n/2. ✓ ∎ For n = 500: 500·499/2 = 124,750, the comparison count of quicksort on sorted input in video 4.

(d) Proof. P(n): C(n) = 2F(n + 1) − 1. Base cases: C(0) = 1 = 2F(1) − 1 and C(1) = 1 = 2F(2) − 1 (F(1) = F(2) = 1). ✓ Step (n ≥ 2, assume P(n − 1) and P(n − 2)): C(n) = 1 + C(n − 1) + C(n − 2) = 1 + (2F(n) − 1) + (2F(n − 1) − 1) = 2(F(n) + F(n − 1)) − 1 = 2F(n + 1) − 1. ✓ ∎ Check: F(6) = 8 → 2·8 − 1 = 15; F(11) = 89 → 177; F(31) = 1,346,269 → 2,692,537. ✓ Since F(n) ≈ φⁿ/√5 with φ ≈ 1.618, every step up in n multiplies the call count by about 1.6: exponential.

(a) Claim: for a list sorted in ascending order and any lo ≤ hi + 1 inside the list, search(items, target, lo, hi) returns an index of the target if it occurs in items[lo..hi], and "not found" if it does not. Strong induction on the range length m = hi − lo + 1 ≥ 0. Base m = 0 (lo > hi): the range is empty, the target does not occur, and the function returns "not found". ✓ Step m ≥ 1: then lo ≤ mid ≤ hi. If items[mid] == target the function returns mid, which holds the target. ✓ If items[mid] < target, then because the list is sorted every item of items[lo..mid] is ≤ items[mid] < target, so the target cannot be there: it occurs in items[lo..hi] exactly when it occurs in items[mid + 1..hi]. That range has hi − mid < m items (as mid ≥ lo), so by the induction hypothesis the recursive call answers correctly. The case items[mid] > target is symmetric with items[lo..mid − 1], of length mid − lo < m. ∎ Sortedness is used exactly once: to discard a whole half after one comparison. (On an unsorted list the call can discard the half that contains the target.)

(b) One probe, then a call on a range of length mid − lo = ⌊(m − 1)/2⌋ or hi − mid = ⌈(m − 1)/2⌉. Both are at most ⌊m/2⌋ (for m = 2t the lengths are t − 1 and t; for m = 2t + 1 both are t). So P(0) = 0 and P(m) ≤ 1 + P(⌊m/2⌋). Claim: P(m) ≤ ⌊log₂ m⌋ + 1 for m ≥ 1. Induction on m. Base m = 1: P(1) ≤ 1 + P(0) = 1 = ⌊log₂ 1⌋ + 1. ✓ Step m ≥ 2: ⌊m/2⌋ ≥ 1, so P(m) ≤ 1 + P(⌊m/2⌋) ≤ 1 + ⌊log₂ ⌊m/2⌋⌋ + 1. If 2ᵗ ≤ m < 2^(t+1) then 2^(t−1) ≤ ⌊m/2⌋ < 2ᵗ, so ⌊log₂ ⌊m/2⌋⌋ = t − 1 = ⌊log₂ m⌋ − 1 and P(m) ≤ ⌊log₂ m⌋ + 1. ✓ ∎

(c) m = 1,000: 2⁹ = 512 ≤ 1,000 < 1,024, so ⌊log₂ 1,000⌋ = 9 and the bound is 10. m = 1,000,000: 2¹⁹ = 524,288 ≤ 10⁶ < 2²⁰, so ⌊log₂ 10⁶⌋ = 19 and the bound is 20. These are the numbers the demos print (n = 1000: 10 probes, n = 1000000: 20 probes). Doubling the list from 1,000 to 2,000 raises the bound only from 10 to 11.

(a) On sorted input the last item is the largest, so the partition leaves all other m − 1 items on the left and the right part is empty. A range of m items costs m − 1 comparisons, and the left part is again sorted. So T(n) = T(n − 1) + (n − 1), T(0) = 0, and by Exercise 1(c) T(n) = n(n − 1)/2. For n = 500 that is 124,750, exactly the count the demos print (both languages). The recursion is also n levels deep, which is why 2,000 sorted items overflow Python's default recursion limit in the demo.

(b) At most once. Two items are compared only when one of them is the pivot and the other is in the pivot's current range. After a partition the pivot is in its final place and belongs to no later range, so a pair can be compared only in the step where one of the two is chosen as pivot; that happens once. Probability. Items of rank i < j stay in the same range for as long as no pivot with rank strictly between i and j has been chosen (such a pivot would send one of them left and the other right). Look at the first pivot chosen among the j − i + 1 ranks {i, i + 1, …, j}. While i and j are together, all of these ranks are in the current range and the pivot is uniform on the range, so the first pivot to land in the set is uniform on the set. If it is i or j, they are compared (one is the pivot, the other is in its range). If it is a rank strictly between, they are separated and never compared. Hence P(compared) = 2 / (j − i + 1).

(c) By linearity of expectation, E[C] = Σ over pairs i < j of 2/(j − i + 1). Group by d = j − i (there are n − d pairs with that difference): E[C] = Σ_{d=1}^{n−1} (n − d)·2/(d + 1) ≤ 2n·Σ_{d=1}^{n−1} 1/(d + 1) = 2n·(Hₙ − 1), where Hₙ = 1 + 1/2 + … + 1/n. And Hₙ − 1 = Σ_{k=2}^{n} 1/k ≤ ∫₁ⁿ dx/x = ln n. So E[C] ≤ 2n ln n ≈ 1.39 n log₂ n. For n = 500: 2n ln n ≈ 6,215. (The exact expectation of this sum is 2(n + 1)Hₙ − 4n; for n = 500 that is about 4,806.) The demos measured one run each: 5,116 in Python and 4,744 in Java, both close to the expectation and below the bound. Note what is random: the pivot choices, not the input, so the bound holds for every input, including sorted ones.

(a) To move n disks from A to C with spare B: (1) move the top n − 1 disks from A to B (using C as the spare); (2) move the largest disk from A to C; (3) move the n − 1 disks from B to C (using A as the spare). Base case: with n = 0 disks there is nothing to do.

(b) M(0) = 0 and M(n) = 2M(n − 1) + 1. Unrolling: M(n) = 2M(n − 1) + 1 = 4M(n − 2) + 2 + 1 = … = 2ⁿ·M(0) + (2ⁿ⁻¹ + … + 2 + 1) = 2ⁿ − 1. Proof. P(n): M(n) = 2ⁿ − 1. Base n = 0: 0 = 2⁰ − 1. ✓ Step: M(n + 1) = 2(2ⁿ − 1) + 1 = 2^(n+1) − 1. ✓ ∎ No method does better. Let Opt(n) be the fewest moves. The largest disk has to move at least once. When it moves from its peg to another, no other disk can be on either of those two pegs (a disk on top of it would block it; a disk on the target peg would be smaller than the largest disk, which is not allowed to sit on it), so all n − 1 other disks are on the third peg. Getting them there took at least Opt(n − 1) moves (it is the same puzzle for n − 1 disks), and after the big move they must travel again to the target peg, at least Opt(n − 1) more. So Opt(n) ≥ 2·Opt(n − 1) + 1, and by induction Opt(n) ≥ 2ⁿ − 1. The recursive method is optimal.

(c) Let K(n) be the number of calls: K(0) = 1 and K(n) = 1 + 2K(n − 1), so K(n) = 2^(n+1) − 1 (a complete binary tree with n + 1 levels). The call stack is deepest at the first leaf, n + 1 frames (n = n, n − 1, …, 0), so the depth is linear while the time is exponential. For n = 64: 2⁶⁴ − 1 = 18,446,744,073,709,551,615 moves; at one move per second that is about 5.8 × 10¹¹ years, roughly forty times the age of the universe.

(a) Job A: merge sort (or the library's stable sort): it has to be stable, because equal last names must keep their first-name order; its time is Θ(n log n) for every input; the extra memory is about n items, which the problem allows; the call stack is only about log₂ n ≈ 24 frames deep for n = 10⁷. Quicksort as written here is not stable. Job B: quicksort with a random pivot: in place (no second array), expected n log n comparisons (≈ 1.39 n log₂ n) for every input, and the equal-ints question does not arise (equal ints are indistinguishable, so stability is irrelevant for plain ints). The price is the worst case Θ(n²), which a random pivot makes very unlikely, and a deep stack (see (b)). Merge sort would work but needs a second array, which job B cannot spare.

(b) After the partition recurse on the smaller of the two parts and handle the larger part by looping (update lo/hi and partition again) instead of calling. Each recursive call is on at most half of the current range, so the depth d satisfies n/2ᵈ ≥ 1, i.e. d ≤ log₂ n, whatever the pivots are. The worst-case running time does not improve: it is still Θ(n²) for a pivot that is always extreme (the loop does the same work the larger call would have done). Only the stack space is bounded, which removes the stack overflow but not the slowness. (This chapter's code does not implement the trick; the video only names it.)

(c) Python: sorted and list.sort use Timsort, a stable merge-based sort, for both jobs. Java: Arrays.sort(int[]) (job B) is a dual-pivot quicksort with insertion sort for small ranges; Arrays.sort(Object[]), Collections.sort and List.sort (job A) are TimSort, stable and merge-based. In real programs call the library; the point of this chapter is to know what it trades.

Reference code: solutions/py/ex_hanoi.py, solutions/java/ExHanoi.java. The recursion is exactly Exercise 4(a): the moves for n − 1 disks from src to tmp, then the move (src, dst), then the moves for n − 1 disks from tmp to dst. The list has 2ⁿ − 1 entries, which the tests check; a recursive call makes 2^(n+1) − 1 calls in all (Exercise 4(c)).

Reference code: solutions/py/ex_callcount.py, solutions/java/ExCallCount.java: the recurrence of Exercise 1(d) filled in from n = 2 upwards, one addition per step, O(n) time. Calling naive fib(80) itself would make 75,778,124,746,287,811 calls, about 2.4 years at a billion calls per second, but counting them takes 80 additions. The closed form 2F(n + 1) − 1 from Exercise 1(d) works too (the tests use it as a cross-check). In Java the count for n = 80 still fits in a long; from n = 90 on it would overflow.

Reference code: solutions/py/ex_quickselect.py, solutions/java/ExQuickselect.java. Partition keeps the invariant "a[lo..i−1] < pivot, a[i..j−1] ≥ pivot" while j sweeps from lo to hi − 1; each step compares a[j] with the pivot once, so exactly hi − lo comparisons. Finally the pivot is swapped into position i. Quickselect partitions, and then the pivot's final index p tells where the k-th smallest item is: p = k means the pivot is the answer, k < p means the answer is in the left part, k > p in the right part, so only one side is searched. The invariant "lo ≤ k ≤ hi" holds at every iteration, so the loop ends when p = k. With a random pivot the expected number of comparisons is linear (about 3.4n for the median; we measured a mean of 3.41n for n = 4,000, and never more than 8.2n in 900 runs, which is why the tests allow 12n). With the last item as the pivot, sorted input would cost about n²/2. Sorting first would cost n log n; quickselect saves the log n factor.

is_power_of_two(0) never terminates: 0 is even and 0 // 2 = 0, so the call repeats itself with the same argument until the stack is exhausted (Python raises RecursionError, Java StackOverflowError). The docstring's claims "works for every n ≥ 0" and "always terminates" are false: the only stopping case is n == 1 (and the odd case), and the sequence n, n//2, n//4, … from n = 0 is stuck at 0 and never reaches 1. A recursion needs a base case that every chain of calls reaches; here 0 is a fixed point of the step n ↦ n//2. In Java −1 breaks it too: -1 % 2 is −1 in Java (the remainder keeps the sign of the dividend), so the test n % 2 == 1 is false for negative odd numbers; the method then calls itself with −1 / 2 = 0 and falls into the same loop. In Python −1 % 2 is 1, so is_power_of_two(-1) returns False. Fix: a power of two is positive, so start with if n < 1: return False (Java: if (n < 1) return false;), or avoid recursion: n > 0 and n & (n - 1) == 0. The tests in solutions/ show the failing inputs.

(a) contains([1, 2], 2): lo = 0, hi = 1, mid = 0, items[0] = 1 < 2, so it calls contains(items, 2, mid, hi) = contains(items, 2, 0, 1), the same call, forever (RecursionError / StackOverflowError). contains([1, 3, 5], 5) and contains([1, 3, 5], 4) stall the same way. It looks correct on contains([1, 2, 3, 4, 5], 3) (found at the first middle) and on any target in the left half, because the left branch is mid − 1, which does shrink the range; only the right branch is broken, so tests that never need to go right pass. The false sentence is "Every call works on a smaller part of the list": the right call uses mid, not mid + 1. We have just looked at items[mid] and found it too small, so the range must start after it. Since mid is rounded down, mid == lo whenever hi ≤ lo + 1, and the range does not shrink at all. Fix: contains(items, target, mid + 1, hi). By Exercise 2 the corrected version is correct and ends after at most ⌊log₂ n⌋ + 1 calls. (b) (Java) midpoint(2_000_000_000, 2_100_000_000): lo + hi = 4,100,000,000 does not fit in an int (maximum 2,147,483,647), wraps around to −194,967,296, and dividing by 2 gives −97,483,648, a negative array index. The claim "correct for every pair of valid indexes" is false for arrays with more than 2³⁰ elements. Fixes: lo + (hi - lo) / 2 (hi − lo never overflows when 0 ≤ lo ≤ hi), or the unsigned shift (lo + hi) >>> 1 (the sum is read as an unsigned 32-bit number, which fits). The same line was found in the JDK's own binary search and reported in 2006. A Python int has unlimited size, so (lo + hi) // 2 cannot overflow; that part of the bug is specific to fixed-width integers.