What is the average efficiency of this function?Quick sort algorithm average case complexity analysisHow to calculate the probability that the average of a multinomial process exceeds some valueProbability of swapping elements in an arrayBernoulli Experiment with infinite trials.Understanding Cumulative distribution functionAverage-case cost analysis of the Hiring problem.What is minimum and maximum probabilityProbability of rolling a specific average (4, 5) with a six-sided die over n-rollsDefine a function that has a minimum given these probabilities.what is the average cost of a product, given the cost of each case and its probability
Possible Eco thriller, man invents a device to remove rain from glass
Can I cause damage to electrical appliances by unplugging them when they are turned on?
Storage of electrolytic capacitors - how long?
SOQL query causes internal Salesforce error
Sigmoid with a slope but no asymptotes?
What is this high flying aircraft over Pennsylvania?
When and why was runway 07/25 at Kai Tak removed?
Air travel with refrigerated insulin
Why is participating in the European Parliamentary elections used as a threat?
What's the name of the logical fallacy where a debater extends a statement far beyond the original statement to make it true?
What is the meaning of "You've never met a graph you didn't like?"
Does Doodling or Improvising on the Piano Have Any Benefits?
How to leave product feedback on macOS?
Is there a distance limit for minecart tracks?
Determining multivariate least squares with constraint
How to understand "he realized a split second too late was also a mistake"
I'm just a whisper. Who am I?
El Dorado Word Puzzle II: Videogame Edition
Can I say "fingers" when referring to toes?
Anime with legendary swords made from talismans and a man who could change them with a shattered body
What the heck is gets(stdin) on site coderbyte?
Overlapping circles covering polygon
Given this phrasing in the lease, when should I pay my rent?
Confusion over Hunter with Crossbow Expert and Giant Killer
What is the average efficiency of this function?
Quick sort algorithm average case complexity analysisHow to calculate the probability that the average of a multinomial process exceeds some valueProbability of swapping elements in an arrayBernoulli Experiment with infinite trials.Understanding Cumulative distribution functionAverage-case cost analysis of the Hiring problem.What is minimum and maximum probabilityProbability of rolling a specific average (4, 5) with a six-sided die over n-rollsDefine a function that has a minimum given these probabilities.what is the average cost of a product, given the cost of each case and its probability
$begingroup$
Let's say you had an algorithm which worked to find the minimum and maximum values of an array n values long by looking through each value of the array, comparing it to the current maximum value, then if it wasn't greater than that value, it compared it to the current minimum value (both initially set equal to the value of the first value of the array).
As a result, its best case efficiency function was $(n-1)$, while its worst case is $2(n-1)$. Since both are Big O(n), that means that the average case also has to be Big O(n). The material I have says that its average efficiency is $2n-ln(n)-1$.
I'm not certain why this is the case; if there is a probability p that each element is greater than the current maximum, wouldn't you get a binomial probability distribution centered around $(n-1)*p$ "successes", and an average efficiency of about $2(n-1)(p)+(n-1)(1-p)$? Where does the $ln(n)$ come in? Is it from assuming that you're less likely to find a new maximum value as the maximum value increases, or something?
probability probability-distributions asymptotics
asked Mar 14 at 4:51
nick012000nick012000
1033
New contributor
nick012000 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
Let's say you had an algorithm which worked to find the minimum and maximum values of an array n values long by looking through each value of the array, comparing it to the current maximum value, then if it wasn't greater than that value, it compared it to the current minimum value (both initially set equal to the value of the first value of the array).
As a result, its best case efficiency function was $(n-1)$, while its worst case is $2(n-1)$. Since both are Big O(n), that means that the average case also has to be Big O(n). The material I have says that its average efficiency is $2n-ln(n)-1$.
I'm not certain why this is the case; if there is a probability p that each element is greater than the current maximum, wouldn't you get a binomial probability distribution centered around $(n-1)*p$ "successes", and an average efficiency of about $2(n-1)(p)+(n-1)(1-p)$? Where does the $ln(n)$ come in? Is it from assuming that you're less likely to find a new maximum value as the maximum value increases, or something?
probability probability-distributions asymptotics
asked Mar 14 at 4:51
nick012000nick012000
1033
New contributor
nick012000 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
Welcome to MSE. Please edit and use MathJax to properly format math expressions. BTW, your tags are misleading.
$endgroup$
– Lee David Chung Lin
Mar 14 at 5:17
$begingroup$
What would I even change with that “MathJax” stuff? All my equations look fine to me. Also, how are my tags misleading?
$endgroup$
– nick012000
Mar 15 at 1:35
$begingroup$
For example, the consensus is that $2(n-1)p+(n-1)(1-p)$ looks nicer than 2(n-1)(p)+(n-1)(1-p) and $O(n)$ is better than O(n).
$endgroup$
– Lee David Chung Lin
Mar 15 at 1:37
add a comment |
$begingroup$
Let's say you had an algorithm which worked to find the minimum and maximum values of an array n values long by looking through each value of the array, comparing it to the current maximum value, then if it wasn't greater than that value, it compared it to the current minimum value (both initially set equal to the value of the first value of the array).
As a result, its best case efficiency function was $(n-1)$, while its worst case is $2(n-1)$. Since both are Big O(n), that means that the average case also has to be Big O(n). The material I have says that its average efficiency is $2n-ln(n)-1$.
I'm not certain why this is the case; if there is a probability p that each element is greater than the current maximum, wouldn't you get a binomial probability distribution centered around $(n-1)*p$ "successes", and an average efficiency of about $2(n-1)(p)+(n-1)(1-p)$? Where does the $ln(n)$ come in? Is it from assuming that you're less likely to find a new maximum value as the maximum value increases, or something?
probability probability-distributions asymptotics
asked Mar 14 at 4:51
nick012000nick012000
1033
New contributor
nick012000 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Let's say you had an algorithm which worked to find the minimum and maximum values of an array n values long by looking through each value of the array, comparing it to the current maximum value, then if it wasn't greater than that value, it compared it to the current minimum value (both initially set equal to the value of the first value of the array).
As a result, its best case efficiency function was $(n-1)$, while its worst case is $2(n-1)$. Since both are Big O(n), that means that the average case also has to be Big O(n). The material I have says that its average efficiency is $2n-ln(n)-1$.
I'm not certain why this is the case; if there is a probability p that each element is greater than the current maximum, wouldn't you get a binomial probability distribution centered around $(n-1)*p$ "successes", and an average efficiency of about $2(n-1)(p)+(n-1)(1-p)$? Where does the $ln(n)$ come in? Is it from assuming that you're less likely to find a new maximum value as the maximum value increases, or something?
probability probability-distributions asymptotics
probability probability-distributions asymptotics
asked Mar 14 at 4:51
nick012000nick012000
1033
New contributor
nick012000 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Mar 14 at 4:51
nick012000nick012000
1033
New contributor
nick012000 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Mar 15 at 1:43
nick012000
asked Mar 14 at 4:51
nick012000nick012000
1033
New contributor
nick012000 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Mar 14 at 4:51
nick012000nick012000
1033
asked Mar 14 at 4:51
nick012000nick012000
1033
1033
New contributor
nick012000 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
nick012000 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
nick012000 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$begingroup$
Welcome to MSE. Please edit and use MathJax to properly format math expressions. BTW, your tags are misleading.
$endgroup$
– Lee David Chung Lin
Mar 14 at 5:17
$begingroup$
What would I even change with that “MathJax” stuff? All my equations look fine to me. Also, how are my tags misleading?
$endgroup$
– nick012000
Mar 15 at 1:35
$begingroup$
For example, the consensus is that $2(n-1)p+(n-1)(1-p)$ looks nicer than 2(n-1)(p)+(n-1)(1-p) and $O(n)$ is better than O(n).
$endgroup$
– Lee David Chung Lin
Mar 15 at 1:37
add a comment |
$begingroup$
Welcome to MSE. Please edit and use MathJax to properly format math expressions. BTW, your tags are misleading.
$endgroup$
– Lee David Chung Lin
Mar 14 at 5:17
$begingroup$
What would I even change with that “MathJax” stuff? All my equations look fine to me. Also, how are my tags misleading?
$endgroup$
– nick012000
Mar 15 at 1:35
$begingroup$
For example, the consensus is that $2(n-1)p+(n-1)(1-p)$ looks nicer than 2(n-1)(p)+(n-1)(1-p) and $O(n)$ is better than O(n).
$endgroup$
– Lee David Chung Lin
Mar 15 at 1:37
$begingroup$
Welcome to MSE. Please edit and use MathJax to properly format math expressions. BTW, your tags are misleading.
$endgroup$
– Lee David Chung Lin
Mar 14 at 5:17
$begingroup$
Welcome to MSE. Please edit and use MathJax to properly format math expressions. BTW, your tags are misleading.
$endgroup$
– Lee David Chung Lin
Mar 14 at 5:17
$begingroup$
What would I even change with that “MathJax” stuff? All my equations look fine to me. Also, how are my tags misleading?
$endgroup$
– nick012000
Mar 15 at 1:35
$begingroup$
What would I even change with that “MathJax” stuff? All my equations look fine to me. Also, how are my tags misleading?
$endgroup$
– nick012000
Mar 15 at 1:35
$begingroup$
For example, the consensus is that $2(n-1)p+(n-1)(1-p)$ looks nicer than 2(n-1)(p)+(n-1)(1-p) and $O(n)$ is better than O(n).
$endgroup$
– Lee David Chung Lin
Mar 15 at 1:37
$begingroup$
For example, the consensus is that $2(n-1)p+(n-1)(1-p)$ looks nicer than 2(n-1)(p)+(n-1)(1-p) and $O(n)$ is better than O(n).
$endgroup$
– Lee David Chung Lin
Mar 15 at 1:37
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Pls do what @LeeDavidChungLin said - even if this answer resolves your question. :)
Meanwhile, the answer to your last question is Yes...kinda.
There is no assumption that as you progress, Prob(current entry > current max) decreases.
Rather, the assumption is that the input array is randomly ordered to begin with, i.e. any of $n!$ permutations is equally likely.
Under this assumption, when you're examining the $k$th entry, Prob($k$th entry > current max) = $1/k$, because any permutation of the initial $k$-long subsequence is equally likely.
In other words, the decrease in probability is not an assumption by itself, but rather, a consequence of the (very reasonable) "random permutation" assumption.
Finally, $ln n$ comes from an approximation to $sum^n_k=1 1over k$.
answered Mar 14 at 5:59
antkamantkam
2,192212
$endgroup$
add a comment |
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
);
);
nick012000 is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3147573%2fwhat-is-the-average-efficiency-of-this-function%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Pls do what @LeeDavidChungLin said - even if this answer resolves your question. :)
Meanwhile, the answer to your last question is Yes...kinda.
There is no assumption that as you progress, Prob(current entry > current max) decreases.
Rather, the assumption is that the input array is randomly ordered to begin with, i.e. any of $n!$ permutations is equally likely.
Under this assumption, when you're examining the $k$th entry, Prob($k$th entry > current max) = $1/k$, because any permutation of the initial $k$-long subsequence is equally likely.
In other words, the decrease in probability is not an assumption by itself, but rather, a consequence of the (very reasonable) "random permutation" assumption.
Finally, $ln n$ comes from an approximation to $sum^n_k=1 1over k$.
answered Mar 14 at 5:59
antkamantkam
2,192212
$endgroup$
add a comment |
$begingroup$
Pls do what @LeeDavidChungLin said - even if this answer resolves your question. :)
Meanwhile, the answer to your last question is Yes...kinda.
There is no assumption that as you progress, Prob(current entry > current max) decreases.
Rather, the assumption is that the input array is randomly ordered to begin with, i.e. any of $n!$ permutations is equally likely.
Under this assumption, when you're examining the $k$th entry, Prob($k$th entry > current max) = $1/k$, because any permutation of the initial $k$-long subsequence is equally likely.
In other words, the decrease in probability is not an assumption by itself, but rather, a consequence of the (very reasonable) "random permutation" assumption.
Finally, $ln n$ comes from an approximation to $sum^n_k=1 1over k$.
answered Mar 14 at 5:59
antkamantkam
2,192212
$endgroup$
add a comment |
$begingroup$
Pls do what @LeeDavidChungLin said - even if this answer resolves your question. :)
Meanwhile, the answer to your last question is Yes...kinda.
There is no assumption that as you progress, Prob(current entry > current max) decreases.
Rather, the assumption is that the input array is randomly ordered to begin with, i.e. any of $n!$ permutations is equally likely.
Under this assumption, when you're examining the $k$th entry, Prob($k$th entry > current max) = $1/k$, because any permutation of the initial $k$-long subsequence is equally likely.
In other words, the decrease in probability is not an assumption by itself, but rather, a consequence of the (very reasonable) "random permutation" assumption.
Finally, $ln n$ comes from an approximation to $sum^n_k=1 1over k$.
answered Mar 14 at 5:59
antkamantkam
2,192212
$endgroup$
Pls do what @LeeDavidChungLin said - even if this answer resolves your question. :)
Meanwhile, the answer to your last question is Yes...kinda.
There is no assumption that as you progress, Prob(current entry > current max) decreases.
Rather, the assumption is that the input array is randomly ordered to begin with, i.e. any of $n!$ permutations is equally likely.
Under this assumption, when you're examining the $k$th entry, Prob($k$th entry > current max) = $1/k$, because any permutation of the initial $k$-long subsequence is equally likely.
In other words, the decrease in probability is not an assumption by itself, but rather, a consequence of the (very reasonable) "random permutation" assumption.
Finally, $ln n$ comes from an approximation to $sum^n_k=1 1over k$.
answered Mar 14 at 5:59
antkamantkam
2,192212
answered Mar 14 at 5:59
antkamantkam
2,192212
answered Mar 14 at 5:59
antkamantkam
2,192212
answered Mar 14 at 5:59
antkamantkam
2,192212
2,192212
add a comment |
add a comment |
nick012000 is a new contributor. Be nice, and check out our Code of Conduct.
nick012000 is a new contributor. Be nice, and check out our Code of Conduct.
nick012000 is a new contributor. Be nice, and check out our Code of Conduct.
nick012000 is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3147573%2fwhat-is-the-average-efficiency-of-this-function%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
$begingroup$
Welcome to MSE. Please edit and use MathJax to properly format math expressions. BTW, your tags are misleading.
$endgroup$
– Lee David Chung Lin
Mar 14 at 5:17
$begingroup$
What would I even change with that “MathJax” stuff? All my equations look fine to me. Also, how are my tags misleading?
$endgroup$
– nick012000
Mar 15 at 1:35
$begingroup$
For example, the consensus is that $2(n-1)p+(n-1)(1-p)$ looks nicer than 2(n-1)(p)+(n-1)(1-p) and $O(n)$ is better than O(n).
$endgroup$
– Lee David Chung Lin
Mar 15 at 1:37