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

Question

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

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.

Answer 1

Let's take main phrase from your book:

"If you read this sum left to right, it starts with 1 and doubles until it gets to $X$"

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$$

Answer 2

The best approach would be to use induction.

Here is a rough outline of a proof I would create:

• X + X/2 + X/4 + X/8 + ... 1 = 2X - 1 is equivalent to 2^k + 2^(k-1) + ... 2^1 + 2^0 = 2*2^k - 1 for all X=2^k

• Let us create a proposition P(k) which is that: 2^k + 2^(k-1) + ... 2^1 + 2^0 = 2*2^k - 1

• P(0) is true as 2^0 = 2 * 2^0 - 1

• Let us assume that P(k) is true. P(k+1) is whether 2^(k+1) + 2^k + ... 2^1 + 2^0 = 2*2^(k+1) - 1

• 2^(k+1) + 2^k + ... 2^1 + 2^0 = 2^(k+1) + 2*2^k - 1 (Using the fact that P(k) is true)

• 2^(k+1) + 2*2^k - 1 = 2^(k+1) + 2^(k+1) - 1 = 2*2^(k+1) - 1

• Hence P(k) implies that P(k+1)

• Hence, by induction P(k) holds for all natural numbers k.

• Hence, X + X/2 + X/4 + X/8 + ... 1 = 2X - 1 ≈ 2X.