Amortized analysis of virtual, dynamic array using potential function 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&lt;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 &gt; 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?
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.