Amortized Analysis

Appending to a Python list or JavaScript array almost always feels instantaneous, yet every so often the structure allocates a fresh buffer and copies every element into it, an `O(n)` operation. So why do textbooks still call append `O(1)`? Because amortized over a long sequence of appends, the rare expensive operation is paid for by many cheap ones. **Amortized Analysis** is the formal machinery that makes this kind of argument rigorous. This lesson teaches the three classical methods. The **aggregate method** sums the total cost of `n` operations and divides by `n` for a per-operation bound. The **accounting (banker's) method** charges each operation a fixed amount and stores credits on the data structure to pay for future expensive ones. The **potential (physicist's) method** defines a potential function `Phi` and computes amortized cost as actual cost plus the change in `Phi`. You will apply all three to dynamic array doubling, stacks with multipop, and binary counters, and see how amortized `O(1)` differs from worst-case `O(1)` and from average-case analysis. This lesson stands on the shoulders of **Big-O Notation (Upper Bound)** and **Time Complexity Analysis Techniques**. From those lessons you can already analyze a single operation; amortized analysis is what you reach for when the cost of *one* operation is misleading and the right object of study is a *sequence* of operations. Next you will move to **Recurrence Relations**, the other major analysis tool, used when an algorithm's cost is most naturally written recursively rather than as a running total.

Real workloads are rarely uniform. Web caches, compiler symbol tables, and network routers all access the same handful of items thousands of times in a row before moving on. A **Splay Tree** turns that observation into a balancing strategy: every access (search, insert, or delete) drags the touched node to the root through a sequence of rotations, so frequently used keys stay shallow and effectively pay `O(1)` after the first hit. This lesson covers the three splay rotation cases (zig, zig-zig, and zig-zag) that move a target node toward the root in pairs of levels, the modified search, insert, and delete operations that always end with a splay, and the amortized analysis that yields `O(log n)` per operation across any sequence of `m` operations even though individual operations can be `O(n)` in the worst case. You will also meet the working set theorem, which is the formal version of the temporal-locality intuition. In **Binary Search Tree (BST)**, accesses left the tree shape unchanged; balanced variants enforced strict structural invariants. The splay tree refuses both options and instead lets the access pattern itself reshape the tree, with no balance factor or color bit stored anywhere. Next, **Treap (Randomized BST)** keeps the same single-bit-of-extra-state simplicity but uses random priorities (rather than recent access) to control balance.

Every time a function calls another function, the language runtime pushes a frame onto an internal stack; every `return` pops one off. That same Last In, First Out discipline shows up in undo buttons, expression evaluators, browser back navigation, and the call patterns of recursion, which is why **Stack (LIFO)** is one of the first abstract data types every engineer learns. This lesson introduces the four core operations of a stack (`push`, `pop`, `peek`, `isEmpty`), the underflow case you must handle on every pop, and two implementations: a dynamic array stack with amortized `O(1)` push, and a linked list stack with strict `O(1)` push at the head. You will trace stack state through bracket matching, postfix evaluation, and string reversal so the LIFO mental model becomes a tool you reach for instinctively when a problem asks you to remember the most recent thing. In **Arrays & Strings**, you saw that appending to the end of a dynamic array is `O(1)` amortized, which is exactly the cost model for an array-backed stack. **Linked Lists (Singly)** showed that head insertion is unconditionally `O(1)`, which is what makes a linked list the cleanest backing store for a stack with a strict worst-case guarantee. Next, **Queue & Deque** flips the discipline: instead of pulling from the same end you pushed to, you pull from the opposite end, and the implementation gets just a little more interesting.