COMP9123 — Week 2
Foundations & proof moves
Week 2 foundations are the hidden mechanics behind list runtimes: series from shifts, amortised reasoning for growth, and invariants that keep pointer edits safe.
Series behind shifting costs
Whenever an array operation moves many elements, you can model the total work as a sum of small repeated actions.
Middle insertions and deletions are not mysterious: they are repeated assignments. Summations turn 'shift everything after position i' into a precise bound.
| Pattern | Sum model | Result |
|---|---|---|
| Shift one suffix | \(\sum_{j=i}^{n-1} 1\) | \(\Theta(n-i)\) |
| Build by repeated head insertion on an array | \(\sum_{k=1}^{n} k\) | \(\Theta(n^2)\) |
| Geometric capacity growth | \(1+2+4+\dots+2^m\) | \(\Theta(2^m) = \Theta(n)\) total copied elements |
If an append sequence doubles capacity whenever the array is full, the expensive copies happen rarely. The total copied volume across many appends is geometric, not quadratic.
Amortised analysis for dynamic arrays
Week 2's dynamic-size story is the first place where worst-case per operation and average cost over a sequence diverge.
A single resize can cost \(O(n)\), but if capacity doubles, each element is copied only a bounded number of times across a long append sequence, giving amortised \(O(1)\) append.
Worst case
The resize step itself is linear because every existing element moves to a new array.
Aggregate view
Across \(n\) appends, the total number of copied elements is linear, so the average cost per append stays constant.
Why it matters
This is why Python-style dynamic arrays are still a practical default for many list workloads.
Exams often ask you to say both things correctly: the worst-case cost of one append and the amortised cost over many appends.
Pointer invariants for linked-list edits
The lecture examples are easier once you know what must remain true before and after every edit.
Typical invariants are: the head points to the first node, the last node's next is None (unless circular), and every predecessor / successor pair agrees about their connection.
Preserve access to both sides of the splice before editing any link.
Reconnect the new node so the path from head to tail stays continuous with no skipped nodes unless deletion is intentional.
Update any distinguished references such as head, tail, or predecessor / successor links that the representation promises to maintain.
Quick checks
The Week 2 checkpoints now sit directly under the series and amortised sections above, so you can test each idea while it is still fresh.
Tutorial PDF review
Open the tutorial PDF in Materials/, attempt the problems first, then use the checklist below to self-audit whether you really understand the intended reasoning moves.
Tutorial 2 checklist. Make sure you can explain why a node needs both data and links, how traversal works without indexing, and which extra references (like a tail pointer) would change the cost of append or delete operations.