amortized analysis of max heap

Question

Q) Consider an ordinary binary max-heap data structure with n elements that supports insert and extract-max in $O(log(n))$ worst-case time. Give a potential function $\Phi$ such that the amortized cost of insert is $O(log(n))$ and the amortized cost of extract-max is $O(log(n))$, and show that it works.

---

solution

The formula of amortized cost is

$a_n = c_n + \Phi(D_n) - \Phi(D_{n-1})$

Where the potential function: $\Phi (D_n) = n log(n)$.

for insert:

$= c_n + \Phi(D_n) - \Phi(D_{n-1}) \leq log(n) + n log(n) - (n-1)log(n-1) \leq 3 log(n+1) = O(log(n))$

So, the amortized cost of insert is $O(log(n))$

extract max:

$a_n = c_n + \Phi(D_n) - \Phi(D_{n-1}) \leq log(n) + n log(n) - (n+1)log(n+1) = log(n) + n(log(n)) - n log(n+1) - log(n+1) < 0$

So, the amortized cost of extract-max is $O(1)$

---

Assuming this is correct. Could someone explain how they got the potential function?

Answer 1

When doing amortized analysis with a potential function, the potential function appears out of nowhere. One way to come up with a potential function is to try picking some function, and then see if the calculation goes through. If that doesn't work, one can try adjusting the potential function to make the calculation go through. Sometimes we might let $\Phi(\cdot)$ be a placeholder, see what properties it needs to have to make the proof go through, and then try to come up with a function that has those properties.

In other words -- there is not necessarily any systematic way to find a potential function that works. You might need to use trial-and-error, or a lucky guess, or other methods.