REFERENCE SHEET

Data structures & amortized cost

Choose a representation by the operations and guarantees the application needs.

amortized cost = total cost of an operation sequence / number of operations

Definitions

Abstract data type

A collection of operations and their behavior, independent of implementation: a stack is last-in-first-out, a queue first-in-first-out, and a dictionary associates keys with values.

Representation

Arrays offer constant-time indexed access in a word-RAM model. Linked lists offer constant-time insertion after a known node, but finding that node may take linear time.

Amortized analysis

A bound on the total cost of every allowed operation sequence, spread over its operations. It does not assume a random input distribution.

Key theorems

Dynamic-array doubling

Starting with fixed positive capacity, appending n items while doubling capacity when full takes O(n) total element writes and copies. Each append is O(1) amortized, although a resize takes Θ(n) at that moment.

Binary heaps

An array-based binary heap supports finding its extremum in O(1) and insertion or extraction in O(log n) worst-case time. Bottom-up construction takes O(n).

Hash-table qualification

With bounded load factor and suitable uniform hashing assumptions, chaining gives expected O(1) lookup. Worst-case lookup can still take Θ(n).

Notable applications

Scheduling

A heap is a natural priority queue when repeatedly processing the next event.

Graph traversal

A queue supports BFS layers; a stack supports DFS exploration.

Work it out

Try before revealing

01 / Analyze

Starting at capacity 1, append 9 items to a doubling array. How many old elements are copied during resizing?

Hint

List the capacities that become full before the last append.

Solution

Copies occur at capacities 1, 2, 4, and 8, totaling 15. There are also 9 writes of new items. An expensive final operation is compatible with a linear total.

02 / Choose

Which structure naturally supports repeatedly removing the currently smallest item while new items arrive?

Hint

Distinguish minimum access from arbitrary key lookup.