[Solved]: Amortized analysis of virtual, dynamic array using potential function

Problem Detail: 

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?

Asked By : Kelsey

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33901

3.2K people like this

 Download Related Notes/Documents