What is the intuition behind the Potential Function in Amortized Analysis of some algorithm?

Problem Detail: 

I have come across many amortized analysis using a potential function. They all look magical to me. Everything works perfectly but I never got the intuition behind how they come up with such a "magical" potential function which makes everything work. My question is can someone share their experience in developing a potential function for amortized analysis and the intuition behind it?

Asked By : user1105

Answered By : Giovanni Botta

Imagine filling up a huge water tank. Now when you open the faucet you have nice water pressure. The pressure will last probably until the tank is almost empty (depending on its size). At that point you need to refill it to have your constant pressure again, so you make the effort again.

The potential function is the water tank. You do some work that will "last" for a while and "store" the energy used in the potential function, e.g., allocating an new array in dynamic arrays/tables. You won't need to do any more work for a while, e.g., until the size of your array grows too much or shrinks too much. At that point you have used all the energy in your potential function (all the water is gone) and need to recharge (refill the tank).

As far as designing such a function, let's take as example the case of a dynamic array. The main point to bring home here is that the potential function Φ is linear in the input size. The coefficients and constant values matter to a certain point (in physics, what really matters is the derivative of the potential function, or the difference between values of the potential function in different points, so additive constants don't really matter in general). We know the function is linear in this case because the expensive operation that we want to amortize is a linear operation (resizing of the array) and we want to prove that this operation determines the cost of a sequence of operations. So, from a practical standpoint, we could have written Φ = a*n + c, performed our analysis and then assigned reasonable values to our two constants so that the potential is always positive. Note that these coefficients might heavily depend on the details of the algorithm/data structure being analysed. For example it's be interesting to try and change when the array gets resized and the amount by which it gets resized and see if the function still hold and also if the linearity still holds. This is discussed in CLRS.

It's also worth noting that, although possible, it might be impractical or tedious to apply amortized analysis to any algorithm. In many cases simpler approaches, e.g., the use of the master theorem, will suffice. The potential method works well for cases like the dynamic array, where you have an expensive operation that you are trying to "amortize" over a sequence of operations, thus not all the operations have the same cost, but the overall cost of performing a given sequence of operations is well defined (linear in this example).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30543