Data Structures and Amortized Analysis

Introduction and Context

Algorithms operate on data, but the representation of that data strongly influences efficiency. A search procedure over an unsorted array, a balanced search tree, and a hash table may solve the same abstract problem while exhibiting very different time, memory, and locality characteristics. Data structures therefore should not be treated as passive containers. They are algorithmic design decisions that determine which operations are cheap, which are expensive, and how costs evolve over a sequence of operations.

Classical asymptotic analysis usually assigns a worst-case cost to each individual operation. That view is sometimes too pessimistic or too coarse. A dynamic array may occasionally require linear-time resizing, yet a long sequence of insertions can still have constant amortized cost per insertion. Amortized analysis explains this phenomenon without assuming probabilistic input or average-case behavior. It proves a bound on the total cost of a sequence and then distributes that cost across its operations.

This chapter develops the conceptual and analytical foundations of arrays, linked structures, stacks, queues, hash tables, trees, heaps, and disjoint-set structures. It then presents aggregate, accounting, and potential-function methods of amortized analysis, followed by applications to dynamic tables, binary counters, and self-adjusting structures. The emphasis is on design reasoning: selecting a representation, stating invariants, proving correctness, and evaluating trade-offs relevant to AI and machine-learning systems.

Learning Objectives

After studying this chapter, you should be able to:

1. Explain how representation affects the complexity of abstract data-type operations.
2. Compare arrays, linked lists, hash tables, trees, heaps, and disjoint-set structures.
3. State and use invariants for common data structures.
4. Distinguish worst-case, average-case, expected, and amortized complexity.
5. Apply aggregate, accounting, and potential methods to prove amortized bounds.
6. Design data structures for practical AI/ML workloads while considering locality, concurrency, memory, and adversarial inputs.

1. Abstract Data Types and Representation

An abstract data type (ADT) specifies values and supported operations without prescribing implementation. A dictionary ADT, for example, may provide search, insert, and delete. A priority queue may provide insert, minimum, and extract-min. A data structure is a concrete representation plus algorithms implementing the ADT.

A valid implementation must preserve a representation invariant: a condition that is true before and after every public operation. For a binary min-heap, the invariant is that every parent key is no greater than the keys of its children. For a hash table, the invariant includes a defined relationship between a key, its hash value, and the locations examined during lookup.

The complexity of an operation depends on more than its asymptotic count. Important engineering factors include:

• Memory locality: contiguous arrays usually use cache lines more effectively than pointer-rich structures.
• Allocation overhead: linked structures may require one allocation per element.
• Update pattern: frequent insertions in the middle favor different structures from sequential scans.
• Concurrency: fine-grained mutation and synchronization can alter the preferred design.
• Persistence and sharing: immutable structures may simplify parallel and distributed computation.
• Predictability: real-time systems may prefer strict worst-case bounds over low amortized cost.

Asymptotic notation describes growth as input size increases. O(g(n)) is an upper-bound class, Ω(g(n)) a lower-bound class, and Θ(g(n)) a tight bound, where n is an appropriate size parameter. These notations suppress constants and lower-order terms; consequently, empirical performance and hardware behavior remain relevant.

2. Sequential and Linked Structures

Arrays and Dynamic Arrays

A fixed array stores elements in consecutive memory locations. If the first element is at address b and each element occupies w units, the address of index i is b + iw, assuming zero-based indexing and valid bounds. Thus random access is Θ(1). Searching an unsorted array is Θ(n) in the worst case, while binary search on a sorted array is Θ(log n) but requires an ordering and random access.

Insertion or deletion at position i may require shifting n-i elements, giving Θ(n) worst-case time. Appending is constant time only when unused capacity exists.

A dynamic array stores a logical size m and a capacity C, with m ≤ C. When full, it allocates a larger block and copies the elements. If capacity is multiplied by a constant growth factor α > 1, the total copying cost over many appends is linear in the number of appended elements. The precise factor affects memory waste and copying frequency: larger α reduces reallocations but may consume more unused memory.

Linked Lists

A singly linked list stores each element and a pointer to the next node. Given a pointer to a node, insertion immediately after it is Θ(1). Access by rank is Θ(n), because links must be followed sequentially. Doubly linked lists add a predecessor pointer, supporting constant-time deletion when a node reference is available, at the cost of additional memory and more pointer updates.

Linked lists are useful when stable node identity and frequent local insertion or deletion matter. They are often inferior to arrays for scanning because pointer chasing harms locality. A list does not make arbitrary insertion constant time unless the location is already represented by a node pointer; finding that location can still take linear time.

Stacks and Queues

A stack follows last-in, first-out (LIFO) order. push, pop, and top can all be Θ(1) with an array or linked representation. A queue follows first-in, first-out (FIFO) order. A circular array with head, tail, and size fields supports enqueue and dequeue in Θ(1) while avoiding repeated shifting. The invariant is that head and tail identify the logical boundaries modulo capacity.

Stacks support depth-first search, parsing, recursion simulation, and backtracking. Queues support breadth-first search, task scheduling, and level-order traversal. In AI systems, queues also arise in beam-search pipelines, event processing, and producer-consumer architectures; bounded queues additionally provide back-pressure.

3. Hash Tables

A hash table implements a dictionary by mapping a key to an array position. A hash function h(k) maps key k to an index. Collisions occur when distinct keys map to the same index.

In separate chaining, each table slot refers to a collection of entries. If n keys occupy m slots, the load factor is

Here α is dimensionless. Under a simple uniform-hashing assumption, expected chain length is proportional to α, so search, insertion, and deletion are expected Θ(1 + α). If α is maintained as a constant, these operations are expected constant time. Worst-case time is Θ(n) if all keys collide.

Open addressing stores entries within the table itself. A probe sequence determines alternative positions, such as linear probing or double hashing. Deletion requires care: simply clearing a slot can prematurely terminate later searches, so a tombstone or a reorganization strategy is needed. Open addressing typically has good locality but becomes inefficient at high load factors.

Hash-table analysis depends critically on the hash-function model. Expected constant time is not a universal guarantee. Adversarial keys, poor hashing, or denial-of-service inputs can produce severe clustering. Secure systems may use randomized or keyed hashing, while production systems should monitor load factor, collision behavior, resizing cost, and memory overhead.

4. Trees, Heaps, and Disjoint Sets

Search Trees

A binary search tree (BST) maintains the invariant that keys in the left subtree are smaller than the node key and keys in the right subtree are larger, subject to the chosen duplicate policy. Search, insertion, and deletion take time proportional to tree height h. A balanced BST maintains h = Θ(log n), yielding logarithmic worst-case operations. An unbalanced BST can degenerate into a chain with h = Θ(n) and linear operations.

AVL trees maintain a strict balance condition based on subtree heights. Red-black trees use a weaker coloring invariant but limit height to logarithmic order with relatively inexpensive updates. B-trees and related multiway trees are preferred in external-memory systems because one node can hold many keys, reducing disk or page transfers.

Heaps and Priority Queues

A binary heap is a complete binary tree represented compactly in an array. For zero-based indexing, the children of index i are at 2i+1 and 2i+2, when those indices are valid; the parent of a nonroot node is ⌊(i-1)/2⌋. A min-heap satisfies parent key ≤ child key.

The minimum is at the root and can be read in Θ(1). insert and extract-min take O(log n) because an element may move along a root-to-leaf path. Building a heap from an arbitrary array using bottom-up heap construction takes Θ(n), not Θ(n log n). The reason is that most nodes are near the leaves and can move only a small distance. A priority queue is central to Dijkstra's algorithm, event simulation, best-first search, scheduling, and many branch-and-bound methods.

Disjoint-Set Union

A disjoint-set union (DSU), or union-find structure, maintains a partition of elements under make-set, find, and union. With union by rank or size and path compression, a sequence of m operations on n elements has total time O(m α(n)), where α(n) is the inverse Ackermann function. It grows so slowly that it is at most a small constant for all practical input sizes, although it is not mathematically constant.

DSU is used in Kruskal's minimum-spanning-tree algorithm, connected-component computation, image segmentation, and clustering-like workflows. Its efficiency results from restructuring the forest during find; this is a canonical example of a data structure whose individual operations can be expensive in isolation but inexpensive over a sequence.

5. Amortized Analysis

Amortized analysis studies a sequence of operations, not the probability distribution of inputs. If operation costs are c₁, c₂, …, c_m, the amortized cost is an accounting value whose sum is at least the actual total cost. Therefore, if the total cost satisfies

then the average cost per operation in that sequence is at most T(m). This does not claim that each operation costs T(m), and it does not rely on randomly distributed inputs.

Three equivalent methods are especially important.

Aggregate Method

The aggregate method bounds the total cost of any sequence of m operations and divides by m. It is direct and often easiest for dynamic arrays. Its limitation is that it may not assign an intuitive cost to each operation.

Accounting Method

The accounting method assigns an amortized charge to each operation. A charge may exceed the actual cost; the surplus is stored as credit on objects or in a global account. The proof must establish that credit never becomes negative. Credits represent work prepaid by earlier operations and cannot be created without justification.

Potential Method

Let D_i be the data-structure state after operation i, and let Φ(D_i) be a nonnegative potential. If actual cost is c_i, define amortized cost

Summing from 1 to m gives

If Φ(D₀)=0 and potential is always nonnegative, the total actual cost is no greater than the total amortized cost. A good potential function measures stored readiness to pay for future expensive work. It must be defined for every reachable state and should make the initial potential manageable.

6. Worked Applications of Amortized Analysis

Dynamic-Array Append

Suppose a dynamic array begins with capacity 1 and doubles whenever full. Consider m append operations. Ordinary appends cost one placement. Resizing copies 1, 2, 4, … elements. Before the final possible resize, the copied sizes form a geometric series:

where r is the index of the last copying event. Since the total number of copied elements is less than m, total work is less than approximately 2m for placements plus copying, up to initial and boundary constants. Hence total cost is O(m), and append has O(1) amortized cost.

An accounting interpretation charges each append a constant amount: one unit pays for its immediate placement and additional credit is saved for its eventual copy. This does not make a resize itself constant time; it establishes a sequence bound.

Binary Counter

Consider incrementing a binary counter represented by bits. A bit flip costs one. A single increment may flip many trailing 1s to 0 and then flip a 0 to 1, so the worst-case cost is linear in the number of bits. Over m increments, however, bit position j flips at most about m/2^j times. Thus total flips are bounded by

and the amortized cost per increment is O(1). This illustrates why repeated local changes can be cheap in aggregate even when occasional operations are expensive.

Stack with Multi-POP

Suppose a stack supports push, pop, and multipop(k), which removes up to k elements. multipop may cost Θ(k). Yet every element can be pushed once and popped at most once. For any sequence of operations, total pops cannot exceed total pushes, so the total cost is linear in the number of pushes and pops. All three operations therefore have O(1) amortized cost, assuming each removed element incurs constant work.

7. Self-Adjusting and Advanced Structures

Some structures deliberately sacrifice a strict per-operation worst-case bound to obtain strong sequence performance or adaptivity. A splay tree moves an accessed node toward the root through rotations. Its individual operation may take linear time, but a sequence of m operations on n keys has amortized O((m+n) log n) cost under the standard analysis. Splay trees adapt to locality of reference and require no explicit balance metadata.

A useful research perspective is the distinction between amortized and competitive analysis. Amortized analysis compares actual work with a preselected bound for the same structure. Competitive analysis compares an online algorithm with an ideal offline algorithm, often for caching or paging. The two approaches answer different questions and should not be conflated.

Persistence introduces another design dimension. A persistent data structure preserves earlier versions, often through structural sharing. Path copying can make updates logarithmic in balanced trees while retaining old versions. The additional allocations affect memory and garbage collection, but immutability can simplify parallel algorithms and reproducible ML pipelines.

8. Selection for AI and Machine-Learning Systems

Data-structure choice should begin with the dominant operations and workload constraints rather than with a fashionable structure.

• Feature storage: dense numerical tensors favor contiguous arrays and blocked layouts; sparse features favor compressed sparse row/column structures or hash-based representations.
• Nearest-neighbor retrieval: tree-based indexes can be effective in low-dimensional settings, while high-dimensional approximate-nearest-neighbor systems often use graph or inverted-index structures.
• Priority-based search: heaps support frontier management in A*, beam search, and best-first inference.
• Streaming systems: ring buffers and queues provide bounded memory and predictable data flow.
• Categorical encoding and caches: hash tables provide expected constant-time lookup, but collision resistance and memory overhead require attention.
• Graph learning: adjacency lists are space-efficient for sparse graphs; adjacency matrices provide fast edge tests but require quadratic storage.

GPU execution changes the trade-off. Pointer-heavy trees and linked lists often perform poorly because of irregular memory access, whereas arrays, sorted indices, and compact sparse formats support coalesced access. On distributed systems, communication and synchronization may dominate local asymptotic work. A theoretically superior data structure can therefore lose in practice if it causes excessive allocation, cache misses, branch misprediction, or network traffic.

9. Case Study: A Streaming Feature-Processing Service

Background

Consider an illustrative feature-processing service for an online fraud-detection model. It receives events, maintains a short history for each account, assigns urgent cases to workers, and expires old records.

Problem

The initial implementation used a linked list for each account's history, a general-purpose list for pending cases, and linear scans to locate accounts. Under peak load, latency became unpredictable, memory use increased, and expired records were not removed promptly.

Analysis

The workload has four dominant operations: account lookup by identifier, append and expiration of time-ordered events, priority selection by risk score, and bounded buffering. A linked list does not solve the lookup problem, and scanning the pending list makes selection linear. Furthermore, unbounded growth creates a governance and availability risk.

Approach and Solution

The redesigned service uses a hash table for account lookup, a deque or ring buffer for each account's bounded history, and a binary heap for risk-prioritized work. A separate expiration queue stores deadlines; when the earliest deadline is reached, records are removed if still valid. Capacity limits enforce back-pressure. Hash-table resizing uses geometric growth, so reallocation has constant amortized cost, while monitoring records load factor and collision behavior.

The design maintains explicit invariants: each account history contains at most its configured number of events; heap entries satisfy the heap property; expiration processing never deletes a newer replacement incorrectly; and queue occupancy never exceeds its bound.

Outcome

The revised architecture changes account lookup from linear scanning to expected constant time, priority selection from linear scanning to logarithmic update/removal, and history maintenance to constant amortized operations per event. Actual latency still depends on hashing, allocation, contention, and downstream inference, so production evaluation must use percentile latency, memory consumption, collision rates, and overload behavior rather than asymptotic notation alone.

Learning Points

The case demonstrates that data-structure selection is a workload-matching exercise. Amortized bounds explain resizing and bounded maintenance, but they do not guarantee every request is fast. Capacity, adversarial behavior, observability, and failure handling are part of algorithm engineering.

10. Limitations, Governance, and Best Practices

Amortized analysis can hide latency spikes. This is acceptable for batch processing but may be unsuitable for hard real-time control, where worst-case execution time is required. Expected hash-table bounds depend on assumptions that adversaries may violate. Likewise, a logarithmic operation can be slower than a linear scan for small data because constants and locality dominate.

In AI applications, data structures also influence privacy and governance. Caches and histories may retain personal information beyond its legitimate purpose. Systems should apply data minimization, retention limits, access control, encryption where appropriate, and auditable deletion. Data-dependent indexing can expose membership or query patterns, so security review should include structure-level side channels and denial-of-service risks.

Recommended practice is to:

1. Specify the ADT, operations, invariants, and workload.
2. Derive worst-case, expected, and amortized bounds separately.
3. Measure memory, locality, allocation, and tail latency.
4. Test adversarial keys, pathological orders, and capacity boundaries.
5. Document resizing, deletion, failure, and concurrency behavior.
6. Prefer simple representations unless a more complex structure provides a demonstrated benefit.
7. Treat implementation libraries as engineering components whose contracts must be verified.

Chapter Summary

Data structures provide concrete representations for abstract operations, and their invariants make correctness manageable. Arrays offer fast indexed access and strong locality; linked structures support local updates when references are available; hash tables provide expected constant-time dictionaries under suitable assumptions; balanced trees provide logarithmic ordered operations; heaps implement priority queues; and disjoint-set structures support rapidly merging partitions.

Amortized analysis bounds the total cost of an operation sequence rather than the cost of every operation individually. The aggregate method analyzes total work directly, the accounting method stores prepaid credits, and the potential method represents stored work through a nonnegative state function. Dynamic-array resizing, binary counters, multi-pop stacks, and self-adjusting trees show how occasional expensive operations can coexist with efficient long-run behavior.

For AI and ML systems, asymptotic analysis must be combined with locality, memory capacity, parallelism, communication, security, privacy, and tail-latency analysis. A sound design begins with workload requirements and invariants, then validates theoretical predictions through measurement and adversarial testing.

Key Terms

Abstract data type: A specification of values and operations independent of implementation.

Representation invariant: A condition that must hold for a data structure's valid states.

Dynamic array: A resizable contiguous array with logical size and capacity.

Load factor: The ratio of stored hash-table entries to table slots.

Collision: A case in which distinct keys map to the same hash-table position.

Separate chaining: Collision resolution using a collection at each table slot.

Open addressing: Collision resolution by probing within the table itself.

Binary search tree: A tree ordered so that subtree keys follow a node's key.

Balanced tree: A search tree whose height is maintained at logarithmic order.

Heap: A complete tree satisfying a parent-child priority relation.

Priority queue: An ADT supporting insertion and removal of an extreme-priority element.

Disjoint-set union: A structure maintaining a partition under find and union operations.

Worst-case analysis: A bound on the maximum cost of an individual operation or input.

Expected analysis: A bound based on a specified probability model or randomization.

Amortized analysis: A bound on total cost over a sequence of operations.

Aggregate method: Amortized analysis by bounding total sequence cost directly.

Accounting method: Amortized analysis using charges and stored credits.

Potential method: Amortized analysis using changes in a nonnegative state potential.

Load factor: The ratio n/m in a hash table with n entries and m slots.

Memory locality: The tendency of computation to reuse nearby memory locations efficiently.

Review Questions

Short Answer Questions

1. Why does a dynamic array have constant amortized append time despite occasional linear-time resizing?
2. Distinguish an abstract data type from a data-structure implementation.
3. State the heap invariant and the complexities of binary-heap insertion and extraction.
4. Why can a hash table have expected constant-time lookup but linear worst-case lookup?
5. What role does a representation invariant play in algorithm design?

Long Answer Questions

1. Compare arrays, singly linked lists, and doubly linked lists for access, insertion, deletion, locality, and memory overhead.
2. Explain aggregate, accounting, and potential methods, including the conditions needed for a valid amortized proof.
3. Describe balanced search trees, heaps, and disjoint-set union structures and identify representative applications.
4. Analyze the design trade-offs of separate chaining and open addressing under changing load factors.
5. Explain why asymptotic complexity alone is insufficient for selecting data structures in AI/ML systems.

Analytical / Application Questions

1. A dynamic table doubles capacity whenever it becomes full. Formulate an aggregate proof that m append operations take linear total time.
2. Design a data structure for a streaming scheduler supporting account lookup, deadline expiration, and highest-priority selection. State its invariants and expected operation costs.
3. Construct a potential function for a simple stack with push and multipop, and use it to justify constant amortized cost per operation.

Multiple Choice Questions with Answers

Question 1

Which operation is Θ(1) for a fixed array when the index is valid?

A. Random access by index

B. Insertion at the first position

C. Searching an unsorted array

D. Deletion from the middle

Correct Answer: A. Random access by index

Question 2

For a hash table with n entries and m slots, the load factor is:

A. m/n

B. n/m

C. n+m

D. n−m

Correct Answer: B. n/m

Question 3

Which condition is the min-heap invariant?

A. Every child is no greater than its parent

B. The root is always the largest key

C. Every parent key is no greater than its children

D. All leaves are sorted from left to right

Correct Answer: C. Every parent key is no greater than its children

Question 4

What is the amortized cost of append in a geometrically expanding dynamic array?

A. Θ(log n)

B. Θ(n)

C. Θ(n log n)

D. O(1)

Correct Answer: D. O(1)

Question 5

Which amortized-analysis method uses a nonnegative potential function?

A. Aggregate method

B. Potential method

C. Worst-case method

D. Uniform-cost method

Correct Answer: B. Potential method

Question 6

Under suitable hashing assumptions and constant load factor, hash-table lookup is typically:

A. Expected Θ(1)

B. Worst-case Θ(log n)

C. Always Θ(1)

D. Expected Θ(n²)

Correct Answer: A. Expected Θ(1)

Question 7

Bottom-up construction of a binary heap from an arbitrary array takes:

A. Θ(log n)

B. Θ(n)

C. Θ(n log n)

D. Θ(n²)

Correct Answer: B. Θ(n)

Question 8

Which structure is most directly suited to repeatedly selecting the smallest-priority item?

A. Stack

B. Singly linked list without ordering

C. Binary min-heap

D. Circular buffer

Correct Answer: C. Binary min-heap

Question 9

Amortized analysis differs from average-case analysis because amortized analysis:

A. Requires random inputs

B. Bounds total sequence cost without requiring an input probability distribution

C. Only analyzes one operation

D. Always gives a worst-case bound for every operation

Correct Answer: B. Bounds total sequence cost without requiring an input probability distribution

Question 10

With union by rank and path compression, disjoint-set operations over a sequence are bounded by:

A. O(m α(n))

B. O(mn)

C. O(log m) for the entire sequence

D. O(n²) regardless of operations

Correct Answer: A. O(m α(n))