What to hand in

algo with balance, rotate and reload, passing go test ./..., plus a report. This is the search arc's last homework, so it looks across all three lessons.

1. Three indexes, one table

Fill it in with your own measurements at n = 10,000:

	hash (10)	BST (11)	AVL (12)
lookup, shuffled input
lookup, -sorted input
build, shuffled
memory for the whole structure
sorted listing

Comparisons where they mean something; testing.B where they do not. Say which cells you filled with time, and why.

2. When an AVL tree is not worth it

Step 6 listed three conditions under which balancing pays for itself.

Describe a specific program for which none of them holds, and say which structure you would choose for it. Then describe a second one for which all three hold.

Neither of the two may be a library catalogue.

3. The bound against the measurement

TestHeightStaysBoundedOnSortedInput checks 1.4405 · log2(n+2) − 0.3277.

Measure the actual height at n = 10³, 10⁴, 10⁵, 10⁶ and compare with the bound. What is the ratio between them?

Then answer: why does the test check the bound rather than the measured value, when the measured one is always smaller? When would a test written against the measured value be wrong?

4. The counter's boundary, a fourth time

lesson	what the counter could not see
4	memory — zero reported where the heap was growing
6	itself — the crossover moved from n ≈ 6 to n ≈ 3 with the counter in the loop
11	memory layout — the same 5000.5 comparisons, 4.5× different wall time
12	rotations — 23% fewer comparisons, 1.65× slower

List every piece of work algo does that metrics.Counter does not measure. At least four.

Then propose how the instrument could be extended so that rotations become visible — and explain why we did not do that, easy though it would have been.

5. The arc, in your own words

Three paragraphs, one per lesson. Each with:

• the question the structure answers best;
• what it cannot do, or cannot guarantee;
• and one real situation in which you would choose it.

Then a fourth paragraph: the question you would ask first if you had to pick an index for a new program tomorrow. Not the structure — the question.

---

Coursework options

For anyone who wants them, and none is a requirement of this lesson:

• Delete with rebalancing — step 7 explains what it involves and what it costs. The tests already contain everything needed to check it.
• A prefix index — lesson 10's option, still open.
• A red-black tree — the same guarantees, a looser invariant, fewer rotations per insertion. Compare it against your AVL with the same measurements.