Find amortized cost for insertion in binary arrays using accounting/potential methods?
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 &lt; 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:


Creating the initial array: 1.
If the number of elements (before adding the current one) is odd: 2.
If the number of elements is $3\bmod{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*}
&amp;n + 2\lfloor n/2 \rfloor + 4\lfloor n/4 \rfloor + \cdots + 2^k \lfloor n/2^k \rfloor \\ \leq
&amp;n + 2(n/2) + 4(n/4) + \cdots + 2^k(n/2^k) \\ =
&amp;n + n + n + \cdots + n \\ =
&amp;(k+1) n \\ =
&amp;(\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)$.