A fast operation may occasionally have an expensive call. Amortized analysis assesses its cost over a sequence of operations, rather than promising that every call meets the stated bound. It is useful when comparing data structures whose occasional extra work changes their worst-case cost. section 2.6.9
A heap backed by a dynamic array
Heap insert and top have amortized, not worst-case, running-time guarantees when the backing array can grow: a resize may take linear time. Across the work of filling an array with n elements, at most 2n swaps are needed. If a reliable size estimate is available, setting heap capacity in advance avoids resizing as an obstacle to a worst-case logarithmic guarantee. section 2.6.9
Amortized bounds still depend on the other operations an implementation uses. An LRU cache combines constant-time operations with amortized constant-time hash-table operations. In an LFU cache, a Fibonacci heap could make insertion and priority updates amortized constant time, but deleting its top remains logarithmic; storing an entry therefore does not become asymptotically constant time. section 7.4.3 section 7.5.3
Table 7.2 Comparative analysis of performance vs implementation for cache with n elements (view table figure)
| O(1) a |
O(1)a |
||||
| O(1)a |
O(1)a |
||||
| O(1)a |
Compare cache operation costs across implementations; the table marks which constant-time entries are amortized. section 7.4.3
The same distinction matters for deletion in a balanced k-d tree. If troublesome single-branch cases occur only a constant number of times over many removals, the amortized recurrence is Tk(n) = Tk(n/2) + O(n^(1−1/k)). Under that assumption, removal takes amortized O(n^(1−1/k)) time—O(√n) in two dimensions. The assumption is part of the claim, not a worst-case guarantee for each deletion. section 9.3.4
