Amortized Time from Cracking the Coding Interview

Question

I am reading about amortized time in cracking the coding interview. The author begins talking about the sum and I don't understand why we would sum from right to left and how that gives us 2X (X+x/2+...)

"What is the sum of 1 + 2 + 4 + 8 + 16 +... +X? If you read this sum left to right, it starts with 1 and doubles until it gets to X. If you read right to left, it starts with X and halves until it gets to 1. What is then the sum of X+x/2+x/4+x/8+...+1?This is roughly 2X. Therefore, X insertions take O(2X) time.The amortized time for each insertion is O( 1) ."

Answer 1

Let’s try this out on a concrete example. Let’s have X = 128. We want to know what

1 + 2 + 4 + 8 + 16 + 32 + 64 + 128

is. The author’s idea is to write this sum backwards as

128 + 64 + 32 + 16 + 8 + 4 + 2 + 1,

which has the same value as what we started with. She then suggests to think of 64 as 128/2, and 32 as 128/4, and 16 as 128/8, meaning that

128 + 64 + 32 + 16 + 4 + 2 + 1

= 128 + 128 / 2 + 128 / 4 + 128 / 8 + 128 / 16 + 128 / 32 + 128 / 64 + 128 / 128

= 128 (1 + 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + 1/64 + 1/128).

So what is this sum? The insight she’s going for is that those fractions add up to at most two. Do you see why that is? If you’re okay with that idea, you can see that the overall sum is at most 2 · 128., twice what we started with.

You can also work out this summation in a different way. First, notice that

1 + 2 + 4 + 8 + ... + X

= 2⁰ + 2¹ + 2² + 2³ + ... + 2^{log₂ X}.

So we’re adding up a series of powers of two. Can we simplify this? Yep! This is the sum of a geometric series, and with a quick trip to Wikipedia we can learn that

2⁰ + 2¹ + 2² + 2³ + ... + 2^k = 2^k+1 - 1 = 2 · 2^k - 1.

In our case, we have k = lg X, so the sum works out to

2·2^{lg X} - 1 = 2X - 1.

So we do see that, indeed, this sum is at most twice X.