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$ – Yuval Filmus Dec 8 '14 at 23:46
  • $\begingroup$ I've edited it. $\endgroup$ – user1887793 Dec 9 '14 at 0:14
  • $\begingroup$ Why the down-votes? This is a legitimate question, similar to some of our reference questions. $\endgroup$ – Yuval Filmus Dec 9 '14 at 8:03
  • $\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 '14 at 10:20
  • $\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$ – Yuval Filmus Dec 9 '14 at 16:41

Your Answer

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

Browse other questions tagged or ask your own question.