Mixing
Average Runtime of this code
$begingroup$
I was working on a problem to find the average case of a for loop that has a 1 step in it. Each element in the input array has a distribution of {0...i} where i is the index of the element.
What threw me off was that, in the for loop there is an if statement that would prematurely end the for loop and this "if statement" would be executed if the value of the array was 50.
The Psuedocode looks somewhat like this:
for i from 0 to n-1:
do something
if L[i] == 50:
do something, and break
and the input of the array are distributed like this:
L[0] = {0}
L[1] = {0, 1}
L[2] = {0, 1, 2}
L[i] = {0, 1, 2, .., i}
With duplicates being allowed and they're independent.
I already realized that there really was no need to look at the summation before index 50 of the array. Further more, the probability of not getting the value of the array was quite obviously i/i+1, however with this being said I do not know how to fully use the expected value theorem to get the expected running time of the program.
I would just like a little tip to get me on track. I feel like im really close to solving this but yet so far, thank you
real-analysis computational-complexity expected-value
asked Jan 28 at 21:20
Ace GokuAce Goku
11
$endgroup$
add a comment |
$begingroup$
I was working on a problem to find the average case of a for loop that has a 1 step in it. Each element in the input array has a distribution of {0...i} where i is the index of the element.
What threw me off was that, in the for loop there is an if statement that would prematurely end the for loop and this "if statement" would be executed if the value of the array was 50.
The Psuedocode looks somewhat like this:
for i from 0 to n-1:
do something
if L[i] == 50:
do something, and break
and the input of the array are distributed like this:
L[0] = {0}
L[1] = {0, 1}
L[2] = {0, 1, 2}
L[i] = {0, 1, 2, .., i}
With duplicates being allowed and they're independent.
I already realized that there really was no need to look at the summation before index 50 of the array. Further more, the probability of not getting the value of the array was quite obviously i/i+1, however with this being said I do not know how to fully use the expected value theorem to get the expected running time of the program.
I would just like a little tip to get me on track. I feel like im really close to solving this but yet so far, thank you
real-analysis computational-complexity expected-value
asked Jan 28 at 21:20
Ace GokuAce Goku
11
$endgroup$
add a comment |
$begingroup$
I was working on a problem to find the average case of a for loop that has a 1 step in it. Each element in the input array has a distribution of {0...i} where i is the index of the element.
What threw me off was that, in the for loop there is an if statement that would prematurely end the for loop and this "if statement" would be executed if the value of the array was 50.
The Psuedocode looks somewhat like this:
for i from 0 to n-1:
do something
if L[i] == 50:
do something, and break
and the input of the array are distributed like this:
L[0] = {0}
L[1] = {0, 1}
L[2] = {0, 1, 2}
L[i] = {0, 1, 2, .., i}
With duplicates being allowed and they're independent.
I already realized that there really was no need to look at the summation before index 50 of the array. Further more, the probability of not getting the value of the array was quite obviously i/i+1, however with this being said I do not know how to fully use the expected value theorem to get the expected running time of the program.
I would just like a little tip to get me on track. I feel like im really close to solving this but yet so far, thank you
real-analysis computational-complexity expected-value
asked Jan 28 at 21:20
Ace GokuAce Goku
11
$endgroup$
I was working on a problem to find the average case of a for loop that has a 1 step in it. Each element in the input array has a distribution of {0...i} where i is the index of the element.
What threw me off was that, in the for loop there is an if statement that would prematurely end the for loop and this "if statement" would be executed if the value of the array was 50.
The Psuedocode looks somewhat like this:
for i from 0 to n-1:
do something
if L[i] == 50:
do something, and break
and the input of the array are distributed like this:
L[0] = {0}
L[1] = {0, 1}
L[2] = {0, 1, 2}
L[i] = {0, 1, 2, .., i}
With duplicates being allowed and they're independent.
I already realized that there really was no need to look at the summation before index 50 of the array. Further more, the probability of not getting the value of the array was quite obviously i/i+1, however with this being said I do not know how to fully use the expected value theorem to get the expected running time of the program.
I would just like a little tip to get me on track. I feel like im really close to solving this but yet so far, thank you
real-analysis computational-complexity expected-value
real-analysis computational-complexity expected-value
asked Jan 28 at 21:20
Ace GokuAce Goku
11
asked Jan 28 at 21:20
Ace GokuAce Goku
11
asked Jan 28 at 21:20
Ace GokuAce Goku
11
asked Jan 28 at 21:20
Ace GokuAce Goku
11
asked Jan 28 at 21:20
Ace GokuAce Goku
11
11
add a comment |
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3091400%2faverage-runtime-of-this-code%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- 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.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3091400%2faverage-runtime-of-this-code%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
