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. Might turn this into a series if I think of more random useless information to talk about. 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 \ge 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 \operatorname{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.

I: $$$\Phi(x) \le \alpha(n) \cdot \operatorname{rank}(x)$$$.

This is trivially true for roots and zero ranks.

For non-root nonzero-rank nodes, notice that $$$\operatorname{level} x$$$ and $$$\operatorname{iter} x$$$ are both nonnegative and they're being subtracted, so there's no way we could be higher.

II. What happens to a non-root node following a path compression or a union?

Since $$$x$$$ is non-root, its own rank $$$\operatorname{rank}(x)$$$ is unchanged.

If $$$x$$$ doesn't have its parent changed, then there is no change in potential.

When node $$$x$$$ has its parent $$$\operatorname{parent} x$$$ changed, $$$\operatorname{rank}(\operatorname{parent} x)$$$ must have (strictly) increased, since its new root had its rank increased by 1. Then either:

$$$x$$$'s $$$\operatorname{level}$$$ increased by 1 or more.

• Then the first term of the potential, $$$(\alpha(n) - \operatorname{level}(x)) \cdot \operatorname{rank}(x)$$$, decreases by $$$\operatorname{rank} x$$$.
• Then in the worst case, the $$$\operatorname{iter}$$$ goes from the maximum possible $$$\operatorname{rank} x$$$ to the minimum possible $$$1$$$, which increases potential by up to $$$\operatorname{rank}(x) - 1$$$.
• Net: potential decreases by 1 or more.

$$$x$$$'s $$$\operatorname{level}$$$ did not change, but $$$\operatorname{iter}$$$ did.

• Then the $$$\operatorname{iter}$$$ must have increased (it could not have decreased). Then the potential must decrease by 1 or more.

$$$x$$$'s $$$\operatorname{level}$$$ and $$$\operatorname{iter}$$$ do not change.

• In this case, there is no change in potential.

Conclusion: all non-root nodes either have no change in potential when a path compression or union happens, or their potential decreases by at least 1 if their $$$\operatorname{level}$$$ or $$$\operatorname{iter}$$$ changes.

Another equivalent statement that we'll use later is that if $$$\operatorname{iter}$$$ increases, or if $$$\operatorname{level}$$$ increases (and $$$\operatorname{iter}$$$ could decrease), then the potential of $$$x$$$ decreases by 1 or more.

III. Union costs $$$\alpha(n)$$$ amortized.

Suppose WLOG that we're merging root $$$x$$$ and root $$$y$$$, and suppose that $$$y$$$ is the new root ($$$x$$$ is attached as a child of $$$y$$$).

Performing the merge operation itself is just $$$O(1)$$$ — check which rank is higher, then adjust parent pointers.

Now for potentials:

• Any non-root node has no change or a decrease in potential, as explained in lemma II above.
• Any root node other than $$$x$$$ or $$$y$$$ has no change in potential, since their potentials are given by $$$\Phi(v) = \alpha(n) \cdot \operatorname{rank}(v)$$$ and their ranks do not change.

For the interesting ones:

$$$x$$$

• Had old potential $$$\Phi_{old}(x) = \alpha(n) \cdot \operatorname{rank}(x)$$$.
• Has new potential $$$\Phi_{new}(x) = (\alpha(n) - \operatorname{level}_{new}(x)) \cdot \operatorname{rank}_{new}(x) - \operatorname{iter}_{new}(x)$$$.
• Since $$$\operatorname{rank} x$$$ does not change, and $$$\operatorname{level} x$$$ and $$$\operatorname{iter} x$$$ are nonnegative, $$$\Phi_{new} \le \Phi_{old}$$$. See lemma I. So $$$x$$$'s potential has no change or a decrease.

$$$y$$$

• Had old potential $$$\Phi_{old}(y) = \alpha(n) \cdot \operatorname{rank}(y)$$$.
• Has new potential $$$\Phi_{new}(y) = \alpha(n) \cdot \operatorname{rank}_{new}(y)$$$.
• The rank of $$$y$$$ can increase by at most 1, so $$$\Phi(y)$$$ increases by at most $$$alpha(n)$$$.

Conclusion: the operation takes $$$O(1)$$$ real time, and the total potential increases by at most $$$O(\alpha(n))$$$. Thus, the operation is amortized $$$O(\alpha(n))$$$.

IV. Find costs $$$\alpha(n)$$$ amortized. (This part is complicated.)

High-level goal: Find goes up the tree to the root, which takes $$$O(s)$$$ time, where $$$s$$$ is the number of steps. We will show that at least $$$s - \alpha(n)$$$ nodes along the path will have their potential decreased by 1 or more. Then, the amortized time would be $$$\alpha(n)$$$, since we pay $$$O(s)$$$ real time but get $$$O(s) - O(\alpha(n))$$$ time back from the bank account.

Consider all $$$s$$$ nodes on the path, and consider their levels. Because the levels are bounded in $$$0 \le \operatorname{level} x \lt \alpha(n)$$$, there are at most $$$\alpha(n)$$$ unique levels.

Take all nodes $$$x$$$ on the path where there exists some $$$y$$$ above (that is not the root, and not necessarily immediately above) with the same level ($$$\operatorname{level} x = \operatorname{level} y$$$). We argue that there are at least $$$s - \alpha(n)$$$ (may be off by a small constant due to off-by-1 errors; I don't care) of these nodes.

• This can be proved by a pigeonhole style argument. There are $$$\alpha(n)$$$ unique levels, so only the topmost node of each level doesn't satisfy our property, and there's $$$\le \alpha(n)$$$ of them. Every other node with the same level below it would be satisfied by the top node with the same level.

High-level goal 2: Now we show that for each of these nodes $$$x$$$ with an equal-levelled distant-parent $$$y$$$, its potential decreases by at least 1. This will pay for the find.

Basically, the original structure looks like $$$x \rightarrow ... \rightarrow y \rightarrow ... \rightarrow r$$$ where $$$r$$$ is the root.

We can apply $$$A_{\operatorname{level} x}$$$ at least $$$\operatorname{iter} x$$$ times to $$$\operatorname{rank}(x)$$$ without exceeding the rank of the parent of $$$x$$$. Which means we can apply it at least $$$\operatorname{iter} x$$$ times without exceeding the rank of $$$y$$$, since $$$y$$$ is either the parent of $$$x$$$ or is above the parent of $$$x$$$ and thus has rank at least that of the parent of $$$x$$$.

Then we can apply $$$A_{\operatorname{level} x}$$$ at least one more time, because you can apply $$$A_{\operatorname{level} y} = A_{\operatorname{level} x}$$$ at least once to the rank of $$$y$$$ without exceeding the rank of $$$y$$$'s parent. Of course, the rank of the root is at least that of $$$y$$$'s parent.

In total, we just found that we can apply $$$A_{\operatorname{level} x}$$$ at least $$$\operatorname{iter}(x) + 1$$$ times, without exceeding $$$\operatorname{rank} r$$$.

Now, after the find operation, $$$x$$$ will point directly to the root $$$r$$$. What's the new level and iter of $$$x$$$?

• We can apply $$$A_{\operatorname{level} x}$$$ at least $$$\operatorname{iter}(x) + 1$$$ times, which means either the iter increases by 1, or we overflow the iter and increase the level by 1. In either case, the potential of this node had to decrease by at least 1.

And now we're done!