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

Question

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.

Answer 1

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.