# Amortised Analysis — Time & Space Complexity (Big-O)

Source: https://www.skillbyai.com/en/big-o/a-amortised

> Analyse the average cost per operation over a sequence of operations.

## Expensive sometimes, cheap on average

Some operations are usually cheap but occasionally expensive. **Amortised analysis** bounds the **average cost per operation over any sequence** of operations, which is a worst-case guarantee for the sequence, not an average over random inputs. The classic example is the **dynamic array**. Appending is O(1) until the array is full; then it allocates double the capacity and copies all elements, costing O(k) for k elements. Over n appends starting from capacity 1, the copies cost 1 + 2 + 4 + … + n/2 < n element moves in total, plus n writes for the appends themselves, so the total is **less than 2n**, which is **amortised O(1)** per append. Three techniques exist: the **aggregate method** (total cost ÷ number of operations), the **accounting method** (charge each cheap operation a little extra "credit" that pays for future expensive ones) and the **potential method** (a function of the data structure's state stores prepaid work). Other examples include hash table resizing, union-find with path compression and two-stack queues.

## Rare spikes, low average

Most appends cost one step; occasional resizes cost more, but the average stays constant.

![A bar chart of mostly short equal bars with tall bars at positions that double each time, and a flat dashed line just above the short bars.](assets/figures/big-o/section-7-map.svg) — Figure 7.1 — Costs of dynamic array appends and their amortised average.

## Counting the work of n appends with doubling

Total copies stay below n, so the average per append is constant.

```python
def total_append_work(n):
    capacity, size, work = 1, 0, 0
    for _ in range(n):
        if size == capacity:
            work += size          # copy every existing element to the new array
            capacity *= 2
        work += 1                 # write the new element
        size += 1
    return work

# for n = 1024: copies = 1 + 2 + 4 + ... + 512 = 1023, writes = 1024
# total = 2047 < 2n  ->  amortised O(1) per append
# growing by a constant amount (e.g. +10) instead of doubling gives O(n^2) total
```

## Growth must be geometric

If an array grows by a fixed number of slots each time, the copies add up to O(n²) for n appends. The amortised O(1) guarantee depends on multiplying capacity, by 2 or by another factor greater than 1.

**Quiz:** Why is appending to a doubling dynamic array amortised O(1) even though some appends cost O(n)?

- [x] The total copying cost over n appends is less than about n, so the average per append is constant
- [ ] Resizes never happen
- [ ] Copying is free in modern hardware
- [ ] Amortised means best case

*Answer:* The total copying cost over n appends is less than about n, so the average per append is constant. Geometric growth makes the sum of all copies linear in n.