Accounting method - dynamic array

Question

I want to compute the amortize time of a type of dynamic array (inserting such that if i have no place to insert i am multipling the array by (1+a) (a is between 0 to 1). I need to compute the time with the accounting method. The answer is that i need for each insertion a 2 + $1/a$ coins. I can see why the answer is right, problem is that i don't understand how i was supposed to get to the answer myself so what i am asking for is the way to the solution and the way to approach the question.

Answer 1

The accounting method relies on two arguments. The first is that in any sequence of $n$ operations, you never run out of coins. That is, however you choose to distribute the coins and pay for the operations, no sequence of operation will lead your scheme to a negative balance. The question remains of what this has to do with running time. Now the second argument comes into play, you want the running time to be bounded by the number of chips spent (without this claim, we have nothing relating the amortized running time with our chips distribution scheme). We can conclude that if you have devised a scheme satisfying those two properties, in which $C$ is the maximal amount of chips drawn in a single operation (where the maximum is taken over different types of operations), then the amortized running time is bounded by $C$.

This sheds some light on how to choose the number of chips per operation. I want to draw, for some element $x$, a number of coins that will suffice for all future operations involving $x$ (think of the insertion of $x$ as an element being born, and you attempt to compute how much money you will need from childbirth all the way to college). The tricky thing is that $x$ can be involved in an unbounded number of operations. Each extension of the array requires moving $x$, so I don't know how to determine the number of coins that will suffice to put $x$ through its entire existence. We can overcome this by having each element pay for his part in the first extension after its insertion.

Suppose that you just extended your array from size $k$ to size $\lceil(1+\alpha)k\rceil$. You would need to add an additional $\lceil(1+\alpha)k\rceil - k$ elements before the next extension, which will require $\lceil(1+\alpha)k\rceil$ operations. Let us try to construct our distribution scheme in such a way that only those new elements would pay for the next extension. Let $C$ be the number of coins requested for each insertion which allows this. It suffices that $C\cdot \left(\lceil(1+\alpha)k\rceil - k\right)\ge \lceil(1+\alpha)k\rceil$, or equivalently $C\ge\frac{\lceil(1+\alpha)k\rceil}{\lceil(1+\alpha)k\rceil - k}$. Since $\frac{\lceil(1+\alpha)k\rceil}{\lceil(1+\alpha)k\rceil - k}\le 1+\frac{k}{\lceil(1+\alpha)k\rceil - k}\le 1+\frac{k}{(1+\alpha)k-k}=1+\frac{1}{\alpha}$, it suffices to ask for $1+\frac{1}{\alpha}$ coins. Recalling that you also need a coin for the insertion itself yields the desired result of $2+\alpha^{-1}$.