Time complexity of ArrayList Insertion : Calculating sum of X + X/2 + X/4 + X/8 + ... 1
Let's take main phrase from your book:
&quot;If you read this sum left to right, it starts with 1 and doubles until it gets to $X$&quot;
This means, that $X=2^k$, for some $k$. So, simply using geometrical progression, we have
$$1+2+4+\cdots+2^k=\frac{X}{2^k} +\frac{X}{2^{k-1}} + \cdots+\frac{X}{2^2}+\frac{X}{2}+ X = \frac{1-2^{k+1}}{1-2}=2^{k+1}-1=2X-1$$