Chapter 10. Complexity and Sorting: Your First Delegation

Learning objectives

After this chapter you should be able to:

Do unaided:

Explain Big-O and Big-Theta, and derive a bound for a loop nest or a recursive sort by counting its dominant operation.
Trace insertion, merge and quick sort by hand, counting comparisons, and say which are stable as written.
Predict a log-log slope from a bound, and estimate the slope from a timing table.
Name the input that makes a first-element-pivot quicksort quadratic, and draw its recursion tree.
Write a spec for a sort: header, tests, complexity budget and ownership of its temporaries.

May delegate:

Merge sort and quicksort to the Pair, from your spec, and hostile inputs to the Adversary; you derive the bound and make the final call.

Opening case

A composite case, not a real student or course.

Jonah finished insertion sort for the station's readings on Monday night, after two hours and a page of traces. On Tuesday the Pair phase began: for PA3, students could hand the faster sorts to an agent, as long as they wrote the spec first and audited every line that came back.

The chapter continues from here.

The loop in this chapter

Open a step to see what it asks of you and how it plays out in the Pair phase.

Predictthe bound and the slope for each sort on random, sorted, reverse and equal input, written before any timing; the comparison counts for Listings 10.1 and 10.3.

Step 1 of 6 · You, no AI

What you hand in: A written prediction: the output, the memory state, the operation count, and how sure you are.

Why this step: A prediction written before the run is the only way to learn whether your model of the machine is right. A miss is the most useful result there is, because it shows exactly where the model is wrong.

The first prediction is never delegated.

Ask yourself: What will this print, what will memory look like when it ends, and how many operations will it take?

Log the prediction in your work log · Predict in every chapter · ← Predict in Chapter 9 · Predict in Chapter 11 →
Writeinsertion sort for struct reading by hand, with its own tests and timings.

Step 2 of 6 · You, no AI

What you hand in: One small piece written by hand, to build the mental model.

Why this step: You can only check what you could have built. Writing a small piece yourself gives you the model you will need to judge the agent's version later.

Ask yourself: Could I write this piece again tomorrow without notes?

Browse the companion code · Write in every chapter · ← Write in Chapter 9 · Write in Chapter 11 →
Specifystn_sort.h with stability, ownership of the temporary, error returns and a complexity budget over named inputs; test_sort.c with edge, stability and hostile-input tests, compiled and failing against stubs.

Step 3 of 6 · You

What you hand in: The header or class interface, unit tests, a complexity budget and the ownership rules.

Why this step: The specification is the contract the code will be held to. Tests written first, a cost budget and ownership rules turn "looks right" into something you can check.

The ownership and lifetime section of a specification is never delegated.

Ask yourself: Who allocates, who frees, what does it cost, and what input would break it?

Prompt and specification templates · Specify in every chapter · ← Specify in Chapter 9 · Specify in Chapter 11 →
Delegatethe Pair implements stn_merge_sort_by_time and stn_quick_sort_by_time from the spec; the Adversary proposes inputs; prompts and transcripts saved.

Step 4 of 6 · The agent

What you hand in: The implementation from your specification, or an explanation in the Tutor phase, with the prompts and transcript saved.

Why this step: The agent does the typing; you keep the judgment. Saving the prompts and the transcript makes the delegation something you can audit afterward.

Pair Pair phase: the agent writes small units from your specification, and you audit every line.

Ask yourself: Did I hand over my specification and tests, and did I save what the agent said?

Prompt templates · Delegate in every chapter · ← Delegate in Chapter 9 · Delegate in Chapter 11 →
Auditline reading against the spec, sanitizer and Valgrind runs, your own recurrence for each function, the harness on four input kinds, and the slope compared with your derivation.

Step 5 of 6 · You and the tools

What you hand in: The Audit Report: tests, sanitizer and Valgrind output, your own cost derivation against a timing plot, the defects found, and a keep-or-rewrite decision.

Why this step: What the agent says is testimony until an instrument confirms it. Tests, sanitizers, Valgrind and a timing plot are evidence.

The final judgment that the code is correct is never delegated.

Ask yourself: What did the sanitizer report, does the timing plot match my derivation, and would I keep this code or rewrite it?

The Audit Report template · Audit in every chapter · ← Audit in Chapter 9 · Audit in Chapter 11 →
Defendwhy this bound, which input breaks a pivot rule, where the temporary is freed.

Step 6 of 6 · You, live

What you hand in: A five-minute oral defense.

Why this step: If you can explain it live, you own it. The oral checks that the understanding is yours and not the agent's.

Ask yourself: Why this bound, what input breaks it, and where is this memory freed?

How the loop works · Defend in every chapter · ← Defend in Chapter 9 · Defend in Chapter 11 →

What agents get wrong here

Patterns observed in agent-written code, to test for, not guarantees. If the agent no longer makes the mistake, your job is to prove it got it right, with the same instrument.

First-element pivot, with "O(n log n)" naming no case

How to catch it Sorted, reverse and all-equal inputs at scale; ASan stack-overflow

Section 10.3.1 · AddressSanitizer

Merge temporary leaked on an early return after the malloc

How to catch it Edge tests at n = 0 and n = 1 with LeakSanitizer

Section 10.3.2 · LeakSanitizer, Tests

A complexity claim with no measurement; "use a random pivot" as a full guarantee

How to catch it Derive the bound; log-log slope on the inputs the spec names, all-equal included

Section 10.3.3 · Timing and log-log plots

An unstable sort where the spec said stable

How to catch it A stability test with many ties and each reading's input position recorded

Section 10.3.4 · Tests

What the chapter covers

10.1 The concept, by hand
- 10.1.1 Input size and the dominant operation
- 10.1.2 Counting insertion sort
- 10.1.3 Big-O and Big-Theta
- 10.1.4 A logarithm is a count of halvings
- 10.1.5 Insertion sort traced, and what "stable" means
- 10.1.6 Merge sort and its recursion tree
- 10.1.7 Quicksort and the partition
- 10.1.8 Choosing the pivot
- 10.1.9 Reading a log-log plot
10.2 Predict and check
- 10.2.1 The timing harness
- 10.2.2 What the measurements say
- 10.2.3 Going deeper than the stack
10.3 What agents get wrong here
- 10.3.1 The first-element pivot
- 10.3.2 Leaked merge temporaries
- 10.3.3 Complexity claims with no measurement
- 10.3.4 An unstable sort where stability was specified
10.4 Working with the agent: the first delegation
- 10.4.1 Handing over
- 10.4.2 Auditing what comes back
10.5 Lab: Quadratic to linear, then PA3
10.6 Defend it

Cost thread

From this chapter on, every Audit Report derives a bound rather than stating one: input size, dominant operation, count or recurrence, case, and a slope from the harness that confirms or refutes it. You should be able to rebuild Table 10.5 from memory.

Summary

A cost counts the dominant operation as a function of input size, separately for best, worst and average case; a bound names its case. O is a ceiling; Θ bounds from both sides.
Insertion sort is Θ(n) on sorted input and Θ(n²) in the worst case; merge sort is Θ(n log n) on every input because its recursion tree has log₂ n levels of n work; first-element-pivot quicksort is Θ(n²) on sorted input and recurses n levels deep.
A running time c · nᵏ is a line of slope k on a log-log plot; with n doubling, slope ≈ log₂(t₂ / t₁). A first-element-pivot quicksort was about 190 times slower on 64,000 sorted integers than on random ones, and overflowed the stack on a million reversed ones.
Stability, the pivot rule and a temporary's lifetime are spec decisions, caught by a test with ties, hostile inputs at scale, and leak checkers.
The first delegation works when the student writes header, tests, budget and ownership rule first, the Pair writes only the code, and every Audit Report derives its own bound.

Key terms

input size: the quantity, usually n, that measures how big a problem instance is and that cost is expressed in.
dominant operation: the operation executed most often, whose count sets the growth of the total cost.
Big-O: f(n) is O(g(n)) if f(n) ≤ c · g(n) for all n ≥ n₀, for some positive constants c and n₀; an upper bound.
Big-Omega: f(n) is Ω(g(n)) if f(n) ≥ c · g(n) for all n ≥ n₀; a lower bound.
Big-Theta: f(n) is Θ(g(n)) if it is both O(g(n)) and Ω(g(n)); a tight bound.
bound: a statement, in asymptotic notation and for a named case, of how fast a cost grows.
recurrence: an equation that defines the cost of a problem in terms of the cost of smaller instances of the same problem.
recursion tree: a drawing of a recursive algorithm's calls, level by level, used to add up their work.
slope (of a log-log plot): the exponent k in t ≈ c · nᵏ, estimated as log₂(t₂ / t₁) when n doubles.
timing harness: a program that times code at increasing input sizes, checking its output.
stable sort: a sort that keeps elements with equal keys in their original relative order.
pivot: the element quicksort partitions around.
partition: rearranging a range around the pivot, smaller elements first.
in place: needing no extra memory beyond the input except a constant amount and the recursion stack.
extra space: memory an algorithm needs beyond the input itself.

Companion code

15 files for this chapter, compiled with the book's flags.

Read the code Download ch10.zip

Connections

Where this chapter and another point to each other most often.

Chapter 2: The Working Loop
Why it is wrong. The sentence is testimony, not evidence (Chapter 2's trust ledger).
Chapter 3: Control Flow, Functions, Recursion, and Counting Operations
Chapter 3 started the counting habit and Chapter 8 drew the first log-log plot; here the habit gets its formal vocabulary. ### 10.1.1 Input size and the dominant operation The input size is the number that grows when the problem gets bigger.
Chapter 8: Growable Arrays and Linked Lists: The Cost of Growth
Chapter 3 started the counting habit and Chapter 8 drew the first log-log plot; here the habit gets its formal vocabulary. ### 10.1.1 Input size and the dominant operation The input size is the number that grows when the problem gets bigger.
Chapter 9: Files, Bits, and Function Pointers: ADTs Behind a Header
The harness picks one through a function pointer (Chapter 9).
Chapter 11: Specify First: Abstract Data Types
Chapter 11 develops specs in full; here you need four parts. 1.

See it on the map

10 Complexity and Sorting: Your First Delegation