6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 1. Please don't cross-post on multiple StackExchange sites; it violates site rules. 2. "Can someone share their experience?" is too broad. This site is for specific, answerable questions, not open-ended questions or questions where every answer is valid. See cs.stackexchange.com/help/dont-ask. I invite you to edit your question to narrow it down. For instance, is there an example of a problem where you are struggling to come up with a potential function? $\endgroup$ – D.W. Oct 3 '14 at 15:53
  • $\begingroup$ Sorry, I am a new user & I didn't get myself familiar with these rules. Will be careful in future. I have deleted the question on the cstheory site. And regarding the second point, I am generally facing problem in tackling textbook problems in which you have to come up with a potential function for amortized analysis. So I want some intuition & general strategy on how to come up with a potential function. $\endgroup$ – user1105 Oct 3 '14 at 17:38
  • $\begingroup$ Have you read the chapters on the topic in these textbooks? What you are asking here is, please write a textbook chapter. I agree that this is too broad. $\endgroup$ – Raphael Oct 4 '14 at 8:30
  • $\begingroup$ For example, to do an amortized analysis of binary min-heap data structure for Extract-Min operation and to show it to be O(1), what potential function can we define and also how will we get to it? PS: I'm following CLRS. $\endgroup$ – user1105 Oct 4 '14 at 11:16
6
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Very nice, Giovanni! Good stuff. $\endgroup$ – D.W. Oct 4 '14 at 2:25
  • $\begingroup$ Thats a really nice explanation. Thanks a lot! $\endgroup$ – user1105 Oct 4 '14 at 11:10

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.