Our next topic on amortized analysis is a parallel to the Banker’s Paradigm. This new approach, the physicist’s paradigm, is a little more mathematically rigorous, but ultimately should produce the same answer (or same type of answer) as its money-grubbing counterpart. Although both techniques should produce the same result, it is worth understanding both because often times problems are more easily understood when phrased as one or the other.
So what is it?
Think back to your last physics class, remember gravity? If you took any introduction to physics you likely learned about gravitational potential energy, which is the amount of energy stored in an objects distance from the earth. If you take a one kilogram ball and raise it one meter off the ground, you have bestowed it with 9.8 joules of energy. Releasing the ball also releases that energy, which can be seen when the ball falls to the ground. Now, if you remember this, you might also remember that it doesn’t matter what path the ball takes when you lift it up one meter. All that matters for the calculation of gravitational potential energy is the initial and final position.
How do we use it?
So what does this have to do with algorithms? Well, lets look at each step of an algorithm through the lens of energy functions. We are going to use this short function to determine how much work is done by our algorithm at each step. Here, a_i is the amortized cost required to get us from step i-1 to step i, while t is the actual cost of doing step i. Phi is a potential energy value for the data structure, and we look at the change in potential between the previous step and the current one. Now, if you are reading this and have no clue how to calculate the potential energy of a data structure, well, you are in the right place.