Find amortized cost for insertion in binary arrays using accounting/potential methods?

Question

Background:

The idea of this data structure is as follows. We will have a collection of arrays, where array $i$ has size $2^i$. Each array is either empty or full, and each is in sorted order. However, there will be no relationship between the items in different arrays. The issue of which arrays are full and which are empty is based on the binary representation of the number of items we are storing. For example, if we had 11 items (where 11 = 1 + 2 + 8), then the arrays of size 1, 2, and 8 would be full and the rest empty.

For inserts, we'll do them like mergesort. To insert the number 10, we first create an array of size 1 that just has this single number in it. We now look to see if $A_0$ is empty. If so, we make this be $A_0$. If not (like in the above example), we merge our array with $A_0$ to create a new array (which in the above case would now be [5, 10]) and look to see if $A_1$ is empty. If $A_1$ is empty, we make this be $A_1$. If not (like in the above example) we merge this with $A_1$ to create a new array and check to see if $A_2$ is empty, and so on.

Further clarification found here.

To be clear about costs, let’s say that creating the initial array of size 1 costs 1, and merging two arrays of size $m$ costs $2m$ (so merging the sorted arrays can be done in linear time).

The claim is that the above data structure has amortized cost $O(\log n)$ per insertion.

1. How to show this using the accounting and potential methods for amortization?
2. What would potential function be?

Initial ideas: Right off the bat it seems that this problem bears a lot of resemblance to the typical binary counter problem. Imagine each array being empty or filled represented by a value of 0 (empty) or 1 (filled), and these values are updated accordingly with insertions. These counters would change when current arrays are completely filled and have to perform merges, which will create a larger filled array and as a consequence several smaller unfilled arrays, changing a lot of 1s (filled) to 0s (unfilled). In the binary counter example the expensive cost of incrementing is dealt with through the potential function which is the number of 1s in the binary counter. The cost for an insertion here is not just incrementing a counter, but paying for costly merges. I do think the idea of a counter perhaps can tie into this problem, but am unsure how it connects to potential method and $O(\log n)$ per insertion. Any thoughts?

Also, found this explanation but it doesn't fully make sense to me. Maybe someone would be willing to elaborate?

Answer 1

Here is a solution using direct calculation (I never liked all the fancy methods). Consider the cost of the first $n$ inserts, and suppose that $2^k \leq n < 2^{k+1}$. Thus only the arrays $A_0,\ldots,A_k$ are active. The cost of the $m$th operation can be broken down as follows:

1. Creating the initial array: 1.
2. If the number of elements (before adding the current one) is odd: 2.
3. If the number of elements is $3\bmod{4}$: 4.
4. And so on.

Observe now that:

• The number of odd numbers among $0,\ldots,n-1$ is $\lfloor n/2 \rfloor$.

• The number of elements $3\bmod{4}$ among $0,\ldots,n-1$ is $\lfloor n/4 \rfloor$.

• And so on.

We conclude that the total cost of the first $n$ operations is $$ \begin{align*} &n + 2\lfloor n/2 \rfloor + 4\lfloor n/4 \rfloor + \cdots + 2^k \lfloor n/2^k \rfloor \\ \leq &n + 2(n/2) + 4(n/4) + \cdots + 2^k(n/2^k) \\ = &n + n + n + \cdots + n \\ = &(k+1) n \\ = &(\lfloor \log_2 n \rfloor + 1)n. \end{align*} $$ We conclude that the amortized cost is at most $\log_2 n + 1 = O(\log n)$.