Dynamic Arrays and Amortized Analysis

Python's list.append, Java's ArrayList.add, and every "growable vector" in every language make the same claim: appending an element costs $O(1)$. But a fixed-size array cannot grow — at some point, appending must trigger allocating a bigger array and copying every existing element into it, an operation that is manifestly $O(n)$, not $O(1)$. The claim "$O(1)$ append" is true only in an amortized sense: averaged over a long sequence of operations, not on every individual operation. This note makes that claim precise using the doubling strategy and proves it three different ways — the aggregate, accounting, and potential methods — because each method generalises to a different family of problems later in the vault, most immediately Union-Find's path-compression bound in Topic 5.