0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 23 at 10:38
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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