Time complexity of ArrayList Insertion : Calculating sum of X + X/2 + X/4 + X/8 + … 1


Here is an excerpt from Cracking Coding Interview book where it’s talking about the time complexity of insertion to an ArrayList.

enter image description here

I am trying to prove that the sum of $X + frac{X}{2} + frac{X}{4} + frac{X}{8} + …. 1 $ is $2X$.

Given,

begin{align}
& X + frac{X}{2} + frac{X}{4} + frac{X}{8} + …. 1 \
& = X (1 + frac{1}{2} + frac{1}{4} + frac{1}{8} + …. frac{1}{X}) \
& = 2^n (frac{1}{2^0} + frac{1}{2^1} + frac{1}{2^2} + frac{1}{2^3} + …. frac{1}{2^n}) \
& = 2^n * S_{n+1}
end{align}

Here, $S_{n+1}$ is the sum upto $n+1$ elements,

begin{align}
S_{n+1} & = frac{1}{2^0} + frac{1}{2^1} + frac{1}{2^2} + frac{1}{2^3} + …. frac{1}{2^{n-1}} + frac{1}{2^n} \
S_{n+1} – frac{1}{2^n} & = frac{1}{2^0} + frac{1}{2^1} + frac{1}{2^2} + frac{1}{2^3} + …. frac{1}{2^{n-1}} \
S_{n+1} – frac{1}{2^n} & = S_n
end{align}

Also,
begin{align}
S_{n+1} & = frac{1}{2^0} + frac{1}{2^1} + frac{1}{2^2} + frac{1}{2^3} + …. frac{1}{2^{n-1}} + frac{1}{2^n} \
2S_{n+1} & = 2 + frac{1}{2^0} + frac{1}{2^1} + frac{1}{2^2} + frac{1}{2^3} + …. frac{1}{2^{n-1}} \
2S_{n+1} & = 2 + S_n \
2S_{n+1} -2 & = S_n \
end{align}

Now combining both,
begin{align}
S_{n+1} – frac{1}{2^n} &= 2S_{n+1} -2 \
S_{n+1} &= 2 – frac{1}{2^n}
end{align}

As n approaches infinity, $S_{n+1} = 2$

This is as far as I’ve gotten. I am wondering how to continue from here. Also, am I in the right path?


15 minutes later here is what I’ve figured out.

Placing the value of $S_{n+1}$ back to the original expression,

begin{align}
& X + frac{X}{2} + frac{X}{4} + frac{X}{8} + …. 1 \
& = X (1 + frac{1}{2} + frac{1}{4} + frac{1}{8} + …. frac{1}{X}) \
& = 2^n (frac{1}{2^0} + frac{1}{2^1} + frac{1}{2^2} + frac{1}{2^3} + …. frac{1}{2^n}) \
& = 2^n * S_{n+1} \
& = 2^n (2 – frac{1}{2^n})\
& = 2^n * 2 – 1\
& = 2X – 1\
& approx 2X \
end{align}

But I am not sure if it’s correct. I’ve appreciated some input.