So i want to prove that if i choose a potential function for binary heap as any constant*size of the binary heap (n is the number of nodes) then my insert will not have O(logn) amortized cost and extract Max will not have O(1) amortized cost.Insert and extract max have O(logn) as worst time complexity for binary heaps.

Let ci denotes real cost of i−th operation, and ai denotes amortized cost.

Let Φ(Di)=potential after i operations


                          ai= ci + Φ(Di) − Φ(Di−1)
                            = log(n) + c*n - c*(n-1)
                            = log(n) + c(n-n+1)
                            = log(n) + c

So im unsure as to how to prove that this potential function does not get O(logn) insert amortized cost. O(logn) would mean all functions that are less than or equal to xlog(n) (x is any constant).log(n)+c is greater than log(n) but is it less than x(logn+c)? Any help would be appreciated.

  • $\begingroup$ Please take a moment to properly format your post. $\endgroup$ – Yuval Filmus Mar 16 at 22:22
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – D.W. Mar 17 at 0:07
  • 1
    $\begingroup$ What exactly is your question? The amortized running time of Insert and ExtractMax are whatever they are; they don't depend on the potential function you choose. Perhaps you want to prove a lower bound on their amortized cost? If so, you need to find a sequence of operations such that they cost at least (such-and-such). Does this give you a different idea about a direction to try? $\endgroup$ – D.W. Mar 17 at 0:08
  • $\begingroup$ The question that im trying to solve states that give a potential function Φ such that the amortized cost of INSERT is O(log n) and the amortized cost of EXTRACT MAX is O(1) with respect to Φ which i solved. The next part is asking me to prove that for any constant c, the potential function Φ(H) = c×size(H) is not a solution for the above conditions for insert and extract max. $\endgroup$ – kia1791 Mar 17 at 0:17

Your Answer

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

Browse other questions tagged or ask your own question.