Amortized Analysis

Link-Cut tree operations are $O(\log n)$ amortized, not worst-case. Potential function argument: Define potential based on "heavy" vs "light" edges in the preferred path decomposition.

Each access changes $O(\log n)$ light-to-heavy edge classifications amortized. Intuition:

• Splaying moves accessed nodes to root, making future accesses faster
• Access changes preferred paths, but each change is "paid for" by the operation causing it
• Over $m$ operations, total work is $O(m \log n)$

Single operations can be $O(n)$ in worst case, but sequences of $m$ operations take $O(m \log n)$ total.