2
$\begingroup$

I am trying to get a better understanding of Fibonacci Heaps. I noticed the following definition for the potential function. $$ \Phi(F)=|W| +2\cdot \text{# marks}. $$ I do not understand why it is defined that way, or what its significant is. I am hoping somebody can explain it to me.

$\endgroup$
1
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael
    Feb 24, 2018 at 9:48

1 Answer 1

3
$\begingroup$

Because it works.

In amortized analysis, you pick the potential function. While it's usually related to some insight about the data structure or algorithm work, is it per se completely arbitrary. The only important thing is that if you write down the telescoping sum -- which is always set up in the same way! -- you can derive a good estimate.

$\endgroup$

Your Answer

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

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