I'm trying to find out how potential function works. I'm trying to compute an amortised complexity of $n$ operations on dynamic array. To make it simple, assume, that we can't delete items and we can add item only to end of the array, so something like push. Let's assume that allocation is for free and if the array is full, we reallocate new array of double size and copy (cost 1 for each copy) all items into the new array.

It seems that $Ĉ$ - amortised price of one push is $2$. But how to create a potential function?

POTENTIAL_FUNCTION(Di) - $i$ is the number of items in the array

PUSH: $Ĉi$ = 1 + n + 1-n = 2
COPY: $Ĉi$ = i + ??? 

Please could you simple explain how to create potential function for this?

  • 1
    $\begingroup$ I can't tell what you're doing in the calculations in the second half of the question. It looks like you have a candidate potential function there, so why are you asking how to create a potential function? I don't understand what you're asking. Have you read standard textbook explanations of amortized analysis and worked through some examples there by yourself? $\endgroup$
    – D.W.
    Jun 3 '16 at 19:09
  • $\begingroup$ You are aware that you don't need the potential trick here, right? It's easy to calculate the exact amortized cost. $\endgroup$
    – Raphael
    Jun 3 '16 at 23:01

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.