How should I think to choose the potential function in the amortized analysis? More specifically are there techniques or tips for choosing optimal or good potential functions?

  • $\begingroup$ This is a very general question, but one that definitely makes sense. Are there techniques for choosing optimal or good potential functions? Is there a nice list of examples? How does this method related to another techniques for amortized analysis? $\endgroup$ Dec 8, 2014 at 23:46
  • $\begingroup$ I've edited it. $\endgroup$ Dec 9, 2014 at 0:14
  • $\begingroup$ Why the down-votes? This is a legitimate question, similar to some of our reference questions. $\endgroup$ Dec 9, 2014 at 8:03
  • 2
    $\begingroup$ Don't this and this question answer yours? Note that the answer here is likely "choose it so that the calculations go through" with some vague, example-driven intuitions. It's a creative thing. (Other than most of the other general reference questions, btw, @YuvalFilmus). $\endgroup$
    – Raphael
    Dec 9, 2014 at 10:20
  • 2
    $\begingroup$ @Raphael That's exactly the point – for all we know there are some general techniques here. I am just not aware of any, but if somebody else is, I think it would be interesting and useful. $\endgroup$ Dec 9, 2014 at 16:41


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.