Skip to main content

Complexity Analysis Practice

Allow 60–90 minutes. Specify input size and cost units. Attempt before opening the separate solutions.

  1. A1: For each i=0..n-1, set j=1 and execute a body while j<n, doubling j each time. Derive the exact body count for n>=1 and a tight bound.
  2. A2: Solve T(1)=1,T(n)=3T(n/3)+n exactly on powers of three; then solve T(0)=0,T(n)=T(n-1)+n.
  3. A3: For 2T(n/2)+n/log2(n), base T(2)=1 on powers of two, derive the tree sum. State why the lesson's polynomial-gap Master Theorem does not apply.
  4. A4: Start empty/capacity 1. For17 appends, derive copying, total, and maximum single-append cost under doubling and +1 growth. Check the doubling potential at the end.
  5. A5: Explain why O(nW) knapsack DP is pseudo-polynomial when W is binary encoded. Give a family where the bit length grows by one while W doubles.

Repair by tracing tiny cases, deriving the sum, and identifying a matching lower bound. A sampled growth ratio is supporting evidence, not the required proof.