# How to do if a potential function Does not work? Amortized analysis

Here is an example taken from CLRS.

q)Consider an ordinary binary min-heap data structure with n elements supporting the instructions INSERT and EXTRACT-MIN in O(lg n) worst-case time. Give a potential function Φ such that the amortized cost of INSERT is O(lg n) and the amortized cost of EXTRACT-MIN is O(1), and show that it works.

$$\Phi(H) = 2 \cdot (size of heap = n) = 2n$$

insert:

the amortized cost has the formula

$$a_n = c_n + (\Phi_{n+1}) - \Phi_n$$

$$= log(n) + 2(n+1) - 2n = log(n) + 2 = log(n)$$

holds ?

$$a_n = c_n + (\Phi_{n+1}) - \Phi_n$$

$$= log(n) + 2(n+1) - 2n = log(n) + 2 = log(n)$$

delete is a bit different because after operation n goes down by 1 hence

$$a_n = c_n + (\Phi_{n+1}) - \Phi_n$$

$$= log(n) + 2(n) - 2(n+1) = log(n) - 2 = log(n)$$

so delete is obviously wrong since its not O(1) but insert gave correct one. How do I properly show a potential function being incorrect? Is it enough to just show this? Note: I'm not looking to solve the above question just looking how to disprove potential functions.

• A potential function is not "incorrect". At most, it cannot be used to prove a particular bound on amortized running time. To show that is fails to prove a particular bound on amortized running time, use the definition of what it means for a potential function to imply a bound on amortized running time. Mar 23 '19 at 10:38

When you delete, your $$actual$$ $$cost$$, or $$c_n$$ by your notation, is $$log(n)$$.

it means you want: $$\Delta \phi = \phi_{n+1}-\phi_n \approx -log(n)$$

Its not hard to find such potential function that satisfies both:

try $$\phi = nlog(n)$$

for insert:

$$Cost_{insert} = log(n) + (n+1)log(n+1) - nlog(n)$$

$$= log(n)+log(n+1)+nlog(n+1)-nlog(n) = O(log(n))$$

$$Cost_{delete} = log(n) + (n-1)log(n-1) - nlog(n)$$

$$= log(n)-log(n-1)+nlog(n-1)-nlog(n)$$

$$\leq (log(n)-log(n)) +(nlog(n)-nlog(n)) = O(1)$$

All potential functions that satisfy $$\phi(i) \geq 0$$, $$\phi(0)=0$$ are correct, they just may not prove the amortized time you have in mind.