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$
$\endgroup$
5
-
$\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 FilmusCommented Dec 8, 2014 at 23:46
-
$\begingroup$ I've edited it. $\endgroup$– user1887793Commented Dec 9, 2014 at 0:14
-
$\begingroup$ Why the down-votes? This is a legitimate question, similar to some of our reference questions. $\endgroup$– Yuval FilmusCommented 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$– RaphaelCommented 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$– Yuval FilmusCommented Dec 9, 2014 at 16:41
Add a comment
|