Skip to main content

Worked Examples

Work through the model and derivation, then attempt the changed case before consulting solutions. These examples connect to the offline labs.

1. Count the exact loop, then bound it​

For i=0..n-1 and j=0..i-1, count one body operation: total n(n-1)/2. For n>=2 this lies between n²/4 and n²/2, proving Theta(n²). Empty and singleton inputs do zero body operations; loop overhead is a different counted quantity.

For i=1..n, start j=1 and double while j<=i. The inner count is floor(log2(i))+1. An upper bound is n*(floor(log2(n))+1); a matching lower bound comes from the last floor(n/2) outer iterations, each costing Omega(log n). Thus the total is Theta(n log n), not merely O(n log n).

Transfer: if the inner loop instead executes j=1,2,4,... while j<n independently of i, derive the exact count for positive n. See practice A1.

2. Include the leaves in a recurrence​

Let T(1)=1 and T(n)=2T(n/2)+n for powers of two. There are log2(n) internal levels each costing n, plus n leaves. Therefore T(n)=n log2(n)+n, giving32 at n=8. Substitution verifies the base and inductive step.

Transfer: replace the combine cost by1: leaves dominate, and T(n)=2n-1. A logarithmic recursion depth alone never determines total work.

3. One append spike does not refute amortization​

Start empty/capacity 1, double on full, charge one per copy and new write. At n=16, copied elements are1+2+4+8=15, total 31. Append17 copies 16 then writes1, adding17, so total 48. Maximum append cost changed from 9 to17.

Choose Phi=2*size-capacity+1. Initially0; after 16 operations Phi=17, after 17 Phi=3. The exact identity actual_total=3n-Phi_final gives31 and48. A drop in stored potential pays for the resize. Amortized cost3 is not a promise that every append costs at most3.

Transfer: grow capacity by one. At n=16 copying costs120, total 136. Explain why no constant amortized charge works for every length under this policy.

4. Prove the first matching position​

Search a sorted array for the first value at least target. Maintain [lo,hi) with every index below lo having value less than target and every index at or above hi having value at least target. Initially lo=0,hi=n; both outside regions are empty. If a[mid]<target, sortedness permits lo=mid+1. Otherwise hi=mid, preserving mid as a candidate.

Variant hi-lo strictly decreases and is nonnegative. At termination lo=hi, the outside-region statements establish the postcondition, including the return-n case. For [1,2,2,4] and target 2, intervals go [0,4) to [0,2) to [0,1) to [1,1): index 1 after three probes. Returning immediately on equality can return the wrong duplicate.

Transfer: trace target 3 and empty input; outputs are (3,2) and (0,0) for this implementation.

5. Greedy proves one objective​

Jobs are half-open intervals; touching endpoints are compatible. For maximum count, choose the earliest finishing job g. In a nonempty optimum ordered chronologically, replace the first job o with g. Since g ends no later than o, every later job remains feasible and count is unchanged. Induct on the residual jobs starting at or after g's end. Sorting plus one scan costs O(n log n).

For jobs (0,2,2),(2,4,2),(0,4,9),(4,5,1) listed as (start,end,value), greedy selects indices 0,1,3, count3 but value 5. Weighted optimum chooses2,3, value 10. The exchange preserved count, not total value. This is a specification change, not an implementation bug.

6. Weighted scheduling needs a complete DP contract​

Sort jobs by (end,start,original index). Let p(i) be the number of earlier sorted jobs finishing no later than job i starts. Define D[i] as the maximum value among the first i sorted jobs, D[0]=0. For one-based i, either omit job i or take it with an optimum from its compatible prefix:

D[i] = max(D[i-1], value_i + D[p(i)]).

For the previous example, sorted original indices are0,2,1,3; p values are0,0,1,3. D is [0,2,9,9,10]. Backtracking chooses original indices 3 then2; reversing gives2,3. A value without a valid witness can hide a reconstruction error.

Sorting costs O(n log n); binary predecessor searches cost O(n log n); DP and reconstruction each cost O(n). Storage is O(n). Repeated linear predecessor scans or storing full copied schedules per cell can make an implementation quadratic despite the recurrence's short appearance.

Transfer: change the long job's value from 9 to3. Now indices 0,1,3 yield optimal value 5. Derive the changed table before running code.