1
$\begingroup$

You often want to implement an array $A$ where the length fluctuates over time. If at some point $A$ has length $n$, then you would like to use space $O(n)$. Consider the following: At all moments, a virtual array $A[0...n-1]$ is simulated by an actual array $B[0...m-1]$ where $m\ge n\ge 1$. Initially, $m=n=1$.

Extend: If $n<m$: increment $n$ and set $B[n-1] = NULL$. Else: set $m=2m$, allocated a new array $B'$ with length $m$, copy $B[0...n-1]$ to $B'[0...n-1]$, deallocate $B$, rename $B' $to $B$, increment $n$, and set $B[n-1] = NULL$.

Show, using a potential function, that the amortized cost of $N$ extend operations is $O(N)$.

The potential function I was thinking of using was $r(s)$ defined as the number of elements in the virtual array $A$ at time $s$. So $r(0) = 0 \le r(s)$ for $s > 0$.

However, when I calculate the potential of the extend operation, I get $r(s+1)-r(s) = n+1-n = 1$ (i.e. the number of elements in the array after the operation minus the number of elements in the array before the operation). Yet, the actual amount of work seems to be much higher in the "else" case $\Rightarrow 2m$ (to allocate new array $B'$) $+n$ (to copy from $B$ to $B'$) $+m$ (to deallocate $B$) $+3$ (to rename, increment, and set to $NULL$).

So the amortized cost (equal to actual cost + potential cost) is clearly not $O(1)$, and so the cost of $N$ extend operations will not be $O(N)$. What am I doing wrong here?

$\endgroup$
1
$\begingroup$

What am I doing wrong here? You're using the wrong potential function. Keep looking. If you want to know the solution, the Wikipedia page on the potential method contains the answer.

$\endgroup$
  • $\begingroup$ I thought that there wasn't such a thing as a "wrong" potential function as long as you had the property that $r(0) = 0$ and every state $s$ after $0$ satisfies $r(s)\ge 0$. $\endgroup$ – Kelsey Dec 6 '14 at 2:17
  • 2
    $\begingroup$ That's correct, every potential function gives you a valid bound. But some potential functions give you better bounds than others. Consider for example the constant potential function – it doesn't give you anything better than non-amortized analysis. The point of the potential method is to find a potential function which allows you to prove a good upper bound on the amortized complexity. Not every potential function will do, as this example shows. $\endgroup$ – Yuval Filmus Dec 6 '14 at 5:37
  • $\begingroup$ Thank you for your response, that makes a lot of sense. It doesn't seem like the Wikipedia answer works for this example, though. The actual cost of the extend operation would be $3m+n+3$. If we use $2n-m$ as the potential function, then the potential difference would be $(2(n+1)-(2m))-(2n-m)=2n+2-2m-2n+m = -m+2$. So that actual cost plus the potential cost would be $(3m+n+3)+(-m+2) = 2m+n+5$, which is not $O(1)$. Am I messing this up somewhere? $\endgroup$ – Kelsey Dec 6 '14 at 7:25
  • $\begingroup$ Wikipedia suggests using $C(2n-m)$ for an appropriate constant $C$. See if that helps. $\endgroup$ – Yuval Filmus Dec 6 '14 at 11:39
  • $\begingroup$ If I select $C = 3$, then I get $6n-3m$, so the potential difference is $(6(n+1)-6m)-(6n-3m) = 6n+3-6m-6n+3m = 3-3m$. This gives me the $-3m$ I need when I'm doing total cost+potential cost, but I still get left with an $n$ at the end that I can't subtract off. Is there anyway to fix this? $\endgroup$ – Kelsey Dec 10 '14 at 13:56

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.