Calculating amortized time of set of insertions and deletions from 2-3-4 tree

Question

Question: Prove that a given set of insertions and deletions, has O(1) amortized complexity, when the insertion place is given.

My thoughts: I was advised to define the potential function as X+2Y when X is the number of nodes with 1 key, and Y is the # of nodes with 3 keys. Using Cormen's book, I came to say that the the potential function for each action is bounded between -2 and 2. That's as further I went. I think I'm supposed to use the formula $\sum c_i\hat = \sum c_i +\delta (\phi)$. but don't know how to do it here (what is the cost here?)

Answer 1

In English, the key equation behind amortization with potentials is

amortized cost of an action = - potential before the action
                              + unamortized cost
                              + potential after the action,

where "cost" means something like "running time divided by a fixed constant of your choosing" or "number of nodes visited" (assuming that you limit yourself to constant time per node visited).

When you sum the amortized cost of each action in a sequence, the equation is

total amortized cost = - potential before the sequence
                       + total unamortized cost
                       + potential after the sequence,

because, for two subsequent actions, the potential after the first equals the potential before the second, and the terms cancel. If you solve for total unamortized cost, you can bound it by the total amortized cost plus the maximum difference in potentials.

Since the potential function is given, your job is to bound the amortized cost of each action by some fixed constant. This means proving (i) that the potential doesn't increase by more than a constant over each operation and (ii) that, except for a fixed constant, the cost of each operation can be attributed to a decrease in potential.