Amortized time cost of insertion into an Array list
For the estimate,
$$
n + \frac{n}{2} + \frac{n}{4} + \cdots +1 &lt;n \left(1 + \frac{1}{2} + \frac{1}{4} + \cdots \right) = 2n,
$$
since $1 + 1/2 + 1/4 + \cdots = 2$.

If $n$ insertions take $O(n)$ time, then the amortized time per insertion is $O(n)/n = O(1)$. This is by the definition of amortized time. (More accurately, the amortized time is at most $K$ if $n$ insertions take at most $Kn$ time, for every $n$.)