I'm trying to prove that the amortized time of insertion and deletion on an expanding array is O(1). If the array is full we should multiply it's size it by 1.5, and when its half full we shrink it to be 0.75 of the current size.
I need to prove it using the potential method.
In other words, let's say we have an array of capacity M:
- 1<X = the number we multiply the array with when it's full
- 0<Y<1 = the number we multiply the array size with it when there is less than tM elements, while t<Y
Is there any equation to describe the potential function using X,Y,t?
I have tried so many functions and none of them worked. (Some of these functions worked in all cases but for the case where we delete an element and then shrink the array to be 0.75 its size.)
Well, the whole state of the data structure is captured in just two variables -- the number of full slots and the number of empty slots, so the potential function has to be a function of these. Let's call them F and E.
Growing or shrinking the array only changes E. The array grows when E=0, finishes with E=F/2, and does F amount of work. To pay for that work the potential needs to reduce by O(F), so the potential needs a -E term.
Shrinking the array changes E from F to F/2. The potential needs to decrease by O(F) to pay for the work, so in this case we need a +E term. That seems to be a contradiction, but notice that we only need the +E term when E > F/2 and we only need the -E term when E < F/2, so |E-F/2| works.
The last requirement is that the potential can't go negative. To ensure that |E-F/2| doesn't go negative, we can just add F/2 to get a final potential function of P = |E-F/2| + F/2
Given that potential function, it's easy to show that the actual work done in each operation is in O(1) - O(ΔP), and that Work + ΔP ∈ O(1)