Amortized Analysis & Advanced Structures — Data Structures Course

What you'll learn

Two threads to finish the theory. First, the amortized analysis that justifies "O(1) on average" claims. Then a quick tour of powerful advanced structures you'll meet in the wild: Fenwick and segment trees, skip lists, the LRU cache, and Bloom filters.

By the end you'll be able to:

Explain amortized analysis and its three methods
Recognize what Fenwick trees, segment trees, and skip lists are for
Describe an LRU cache and a Bloom filter

Amortized analysis

A single operation may occasionally be expensive, yet be cheap on average over a sequence. Amortized analysis proves that. We saw it with dynamic arrays (Module 4): most appends are O(1), the rare resize is O(n), but averaged over n appends each is O(1). Three methods make it rigorous:

Method	Idea
`Aggregate`	Total cost of n operations ÷ n
`Banker's (accounting)`	Prepay 'credits' on cheap ops to fund expensive ones later
`Potential`	Track a potential function Φ that stored-up work draws from

Key idea

Amortized O(1) is a guarantee about a sequence, not a single call. It's stronger than average-case: it holds for the worst possible sequence, not just a random one.

Fenwick & segment trees

Suppose you need running range sums of an array that keeps changing. Recomputing is O(n); a Fenwick tree (binary indexed tree) does both point-update and prefix-sum in O(log n), using a beautiful low-bit trick:

Language

fenwick.py

class Fenwick:                # a.k.a. Binary Indexed Tree
    def __init__(self, n):
        self.tree = [0] * (n + 1)

    def update(self, i, delta):    # add delta at index i (1-based)
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & (-i)          # jump to the next responsible node

    def prefix_sum(self, i):       # sum of 1..i
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s

A segment tree is more general — each node stores an aggregate (sum, min, max, gcd…) over a range, supporting range queries and range updates in O(log n). Both are staples of competitive programming.

Skip lists

A skip list is a sorted linked list with extra "express lane" levels that let a search skip ahead, giving O(log n) search, insert, and delete — a simpler, randomized alternative to a balanced tree. Search for 7 by dropping down levels:

A skip list's express lanes

Level 2 · express

H→1→4→9→ ∅

Level 1

H→1→3→4→6→9→ ∅

Level 0 · full

H→1→3→4→6→7→9→10→ ∅

Start at the top-left, move right while you can, drop a level when the next node overshoots. Green = the search path to 7.

LRU cache & Bloom filters

Two structures that combine what you've learned:

Structure	Built from	Superpower
`LRU cache`	Hash map + doubly linked list	O(1) get/put; evicts the least-recently-used item
`Bloom filter`	Bit array + several hash functions	O(1) probabilistic membership in tiny space (no false negatives)
`Segment tree`	Array-backed tree	O(log n) range queries and updates

Note

An LRU cache is a classic interview problem precisely because it composes two structures: the hash map gives O(1) lookup, and the doubly linked list gives O(1) reordering to track recency. Structures are Lego bricks — the best solutions combine them.

Recap & quick check

Key takeaways

Amortized analysis proves an operation is cheap on average across a sequence (e.g. dynamic-array append).
Fenwick trees give O(log n) prefix sums with point updates via the low-bit trick.
Segment trees generalize this to range queries and updates for many aggregates.
A skip list uses randomized express lanes for O(log n) operations without rotations.
An LRU cache = hash map + doubly linked list; a Bloom filter = bit array + hashes.

Quick check

1. Amortized O(1) means:

2. A Fenwick tree efficiently supports:

3. A skip list achieves O(log n) search by:

4. An LRU cache is typically built from:

You now know the whole toolbox. The final module is about choosing from it. Next up: Module 31 — Choosing the Right Structure.