Originally written for my analysis of algorithms class. Shoutout to Prof Mikhail Atallah for being the GOAT

The Tarjan proof is scary. This one is hopefully explained in a way us blues and purples can understand. Also if you are confused anywhere please ask :)

Amortized Analysis Primer

We use the potential method to formally prove amortized time complexity. Here's how it works:

• You start with a potential of 0. It is never allowed to go negative. Think of this as your bank account of CPU cycles.
• You can increase your potential during cheap operations. Think of this as depositing CPU cycles into your bank account that you can use later.
• You can draw your potential during expensive operations, like withdrawing CPU cycles from your bank account.

For a concrete example, consider the std::vector that has to reallocate its internal array if it overflows.

• A push operation, if the array has space, costs $$$O(1)$$$ real time, but let's also deposit $$$O(1)$$$ CPU cycles of potential. The total time complexity is still $$$O(1) + O(1) = O(1)$$$.
• Now suppose we have to enlarge the array by doubling the size at every power of 2. This costs $$$O(n)$$$ time, but can we change it to $$$O(1)$$$?
• Yes! Between $$$\frac{n}{2}$$$ and $$$n$$$, we must have accumulated at least $$$O(\frac{n}{2})$$$ potential. We can use that to pay for this operation: it costs $$$O(n)$$$ real time, but since we use $$$O(n)$$$ of potential to pay for it, it actually becomes free! Now our potential is back to zero, but we'll still accumulate enough potential if we have to resize $$$n \rightarrow 2n$$$ down the line.

Also see Chapter 22 of Kentq (better than Benq?)'s book

Ackermann function definition

There's no universal definition; all Ackermann functions defined in a similarly recursive manner behave pretty much the same. I'll use this one:

Where $$$A_{L-1}^{(x+1)}(x)$$$ denotes applying $$$A_{L-1}$$$ to $$$x$$$, recursively, $$$x+1$$$ times.

Essentially, at "layer $$$L$$$", applying $$$A_L$$$ to $$$x$$$ is the same as applying $$$A$$$, one layer lower, $$$x+1$$$ times to $$$x$$$. As you might imagine, this grows very fast. Each "layer" is essentially a hyperoperation: addition, multiplication (repeated addition), exponentiation (repeated multiplication), tetration (repeated exponentiation), etc.

If this was complicated, the only thing you need to remember is that $$$A_{L-1}$$$ applied $$$x+1$$$ times is the same as applying $$$A_{L}$$$ once.

Union by rank & path compression

I will not explain this too much because I assume you're already familiar with it.

Each node $$$v$$$ has a rank $$$\operatorname{rank} v$$$. Importantly, moving up to the parent of a non-root node strictly increases the rank: $$$\operatorname{rank}(\operatorname{parent} v) \gt \operatorname{rank} v$$$.

The rank of a node $$$v$$$ only changes when $$$v$$$ is a root and is union-ed with another tree with root $$$u$$$; then the rank of one of $$$v$$$ or $$$u$$$ is incremented, and the other node is attached as a child to the new root.

Level

Define for node $$$x$$$ (that is not a root and has nonzero rank) its level $$$\operatorname{level} x$$$ as the maximum $$$k$$$ such that

In other words, it's the highest tier of Ackermann function that we can apply to $$$x$$$'s rank, without exceeding $$$x$$$'s parent's rank.

Since the parent's rank is always strictly higher than the node's, $$$k = 0$$$ is always a valid choice, so $$$\operatorname{level} x \gt = 0$$$.

What's the highest possible level? Define the inverse Ackermann function $$$\alpha(n)$$$ as the lowest number $$$k$$$ such that $$$A_k (1) \ge n$$$. Then if $$$\operatorname{rank} x = 1$$$, the minimum (since we said the rank of $$$x$$$ is nonzero), then applying $$$A_{\alpha(n)}$$$ gets us to a number $$$\ge n$$$, and since the max rank of any node cannot exceed $$$n-1$$$, this always exceeds $$$\operatorname{rank}(\operatorname{parent} x)$$$, so $$$\operatorname{level} x \lt \alpha(n)$$$.

Conclusion: $$$0 \le "level" x \lt \alpha(n)$$$.

Iter

Also define $$$\operatorname{iter} x$$$ as the maximum $$$k$$$ such that

In other words, it's how many times can we apply $$$A_{\operatorname{level} x}$$$ while still remaining $$$\le$$$ the parent's rank.

We know from the definition of $$$\operatorname{level} x$$$ that we can apply it at least once.

We also know that if we apply $$$A_{\operatorname{level} x}$$$ a total of $$$\operatorname{rank}(x) + 1$$$ times to $$$\operatorname{rank} x$$$, that's the same thing as applying $$$A_{\operatorname{level}(x) + 1}$$$ once. That would be a contradiction since we shouldn't be allowed to do that (otherwise $$$\operatorname{level} x$$$ would be this value), so $$$\operatorname{iter} x \le \operatorname{rank} x$$$.

Conclusion: $$$1 \le \operatorname{iter} x \le \operatorname{rank} x$$$.

Potential Definition

Define the following potential $$$\Phi(x)$$$ for a node $$$x$$$:

• $$$\Phi(x) = \alpha(n) \cdot \operatorname{rank}(x)$$$, if $$$x$$$ is a root or has rank 0.
• If $$$x$$$ has rank 0, then $$$\Phi(x) = 0$$$.
• $$$\Phi(x) = (\alpha(n) - \operatorname{level}(x)) \cdot \operatorname{rank}(x) - \operatorname{iter}(x)$$$, for non-root nonzero-rank nodes.

I know it seems really arbitrary; I thought that way too. But we will show that this potential works.