Amortized Time from Cracking the Coding Interview

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box;
}

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) ."

asked Jan 4 at 0:34

user9476376

1067

That sounds wrong. In the description, X isn't the number of insertions log2(X)+1 is the number of insertions.

– thc
Jan 4 at 0:42

add a comment |

asked Jan 4 at 0:34

user9476376

1067

That sounds wrong. In the description, X isn't the number of insertions log2(X)+1 is the number of insertions.

– thc
Jan 4 at 0:42

add a comment |

asked Jan 4 at 0:34

user9476376

1067

big-o amortized-analysis

asked Jan 4 at 0:34

user9476376

1067

asked Jan 4 at 0:34

user9476376

1067

asked Jan 4 at 0:34

user9476376

1067

asked Jan 4 at 0:34

user9476376

1067

asked Jan 4 at 0:34

user9476376

1067

That sounds wrong. In the description, X isn't the number of insertions log2(X)+1 is the number of insertions.

– thc
Jan 4 at 0:42

add a comment |

That sounds wrong. In the description, X isn't the number of insertions log2(X)+1 is the number of insertions.

– thc
Jan 4 at 0:42

That sounds wrong. In the description, X isn't the number of insertions log2(X)+1 is the number of insertions.

– thc
Jan 4 at 0:42

add a comment |

1 Answer
1

active

oldest

votes

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 · 2k} - 1.}

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

2·2lg X - 1 = 2X - 1.

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

answered Jan 4 at 0:54

templatetypedef

267k70679897

Wow thank you so much!

– user9476376
Jan 4 at 0:58

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54031713%2famortized-time-from-cracking-the-coding-interview%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

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).

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 · 2k} - 1.}

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

2·2lg X - 1 = 2X - 1.

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

answered Jan 4 at 0:54

templatetypedef

267k70679897

Wow thank you so much!

– user9476376
Jan 4 at 0:58

add a comment |

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).

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 · 2k} - 1.}

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

2·2lg X - 1 = 2X - 1.

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

answered Jan 4 at 0:54

templatetypedef

267k70679897

Wow thank you so much!

– user9476376
Jan 4 at 0:58

add a comment |

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).

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 · 2k} - 1.}

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

2·2lg X - 1 = 2X - 1.

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

answered Jan 4 at 0:54

templatetypedef

267k70679897

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).

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 · 2k} - 1.}

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

2·2lg X - 1 = 2X - 1.

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

answered Jan 4 at 0:54

templatetypedef

267k70679897

answered Jan 4 at 0:54

templatetypedef

267k70679897

answered Jan 4 at 0:54

templatetypedef

267k70679897

answered Jan 4 at 0:54

templatetypedef

267k70679897

Wow thank you so much!

– user9476376
Jan 4 at 0:58

add a comment |

Wow thank you so much!

– user9476376
Jan 4 at 0:58

Wow thank you so much!

– user9476376
Jan 4 at 0:58

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Stack Overflow!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

搜尋此網誌

Bdtjtk