Randomized quicksort partitioning probability
I'm reading Algorithms Illuminated: Part 1, and problem 5.2 states:
Let ɑ be some constant, independent of the input array length n,
strictly between 0 and 1/2. What is the probability that, with a
randomly chosen pivot element, the Partition subroutine produces a
split in which the size of both the resulting subproblems is at least
ɑ times the size of the original array?
Answer choices are:
- ɑ
- 1 - ɑ
- 1 - 2ɑ
- 2 - 2ɑ
I'm not sure how to answer this question. Any ideas?
algorithm sorting quicksort
asked Nov 15 '18 at 4:32
Abhijit SarkarAbhijit Sarkar
7,73474396
add a comment |
I'm reading Algorithms Illuminated: Part 1, and problem 5.2 states:
Let ɑ be some constant, independent of the input array length n,
strictly between 0 and 1/2. What is the probability that, with a
randomly chosen pivot element, the Partition subroutine produces a
split in which the size of both the resulting subproblems is at least
ɑ times the size of the original array?
Answer choices are:
- ɑ
- 1 - ɑ
- 1 - 2ɑ
- 2 - 2ɑ
I'm not sure how to answer this question. Any ideas?
algorithm sorting quicksort
asked Nov 15 '18 at 4:32
Abhijit SarkarAbhijit Sarkar
7,73474396
add a comment |
I'm reading Algorithms Illuminated: Part 1, and problem 5.2 states:
Let ɑ be some constant, independent of the input array length n,
strictly between 0 and 1/2. What is the probability that, with a
randomly chosen pivot element, the Partition subroutine produces a
split in which the size of both the resulting subproblems is at least
ɑ times the size of the original array?
Answer choices are:
- ɑ
- 1 - ɑ
- 1 - 2ɑ
- 2 - 2ɑ
I'm not sure how to answer this question. Any ideas?
algorithm sorting quicksort
asked Nov 15 '18 at 4:32
Abhijit SarkarAbhijit Sarkar
7,73474396
I'm reading Algorithms Illuminated: Part 1, and problem 5.2 states:
Let ɑ be some constant, independent of the input array length n,
strictly between 0 and 1/2. What is the probability that, with a
randomly chosen pivot element, the Partition subroutine produces a
split in which the size of both the resulting subproblems is at least
ɑ times the size of the original array?
Answer choices are:
- ɑ
- 1 - ɑ
- 1 - 2ɑ
- 2 - 2ɑ
I'm not sure how to answer this question. Any ideas?
algorithm sorting quicksort
algorithm sorting quicksort
asked Nov 15 '18 at 4:32
Abhijit SarkarAbhijit Sarkar
7,73474396
asked Nov 15 '18 at 4:32
Abhijit SarkarAbhijit Sarkar
7,73474396
asked Nov 15 '18 at 4:32
Abhijit SarkarAbhijit Sarkar
7,73474396
asked Nov 15 '18 at 4:32
Abhijit SarkarAbhijit Sarkar
7,73474396
asked Nov 15 '18 at 4:32
Abhijit SarkarAbhijit Sarkar
7,73474396
7,73474396
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
Let there be N elements in the array. If the picked pivot is one of the smallest [Nα] elements in the array, then the left partition's size will be less than Nα. Similarly, if the picked pivot is one of the largest [Nα] elements in the array, the right partition's size will be less than Nα.
Hence, there are N - 2 * [Nα] elements that you can pick such that both partitions have size greater than or equal to Nα. Since the algorithm picks a pivot randomly, all elements have an equal probability of getting picked.
So, the probability of getting such a split is 1 - 2α + O(1 / N).
answered Nov 15 '18 at 5:04
merlynmerlyn
1,77011323
By "pick one of the smallest Nα elements", do you mean pick that element as the pivot? Since α is not an integer,Nαmay be a fraction. Can you pick the 3.5 smallest element from an array? Please elaborate in your answer, don't respond in comments.
– Abhijit Sarkar
Nov 15 '18 at 5:08
@AbhijitSarkar You can truncate the fractional value. The difference is negligible. I have updated the answer with the same.
– merlyn
Nov 15 '18 at 5:20
I think you mean the probability is1 - 2α. Your answer1 - 2α + O(1 / N)is not one of the choices, and doesn't follow from your argument.(N - 2 * Na)/N = 1 - 2a
– Abhijit Sarkar
Nov 15 '18 at 5:24
@AbhijitSarkar That's what I meant by negligible. Some fractional part over N will be left because you can't pick 3.5 elements.
– merlyn
Nov 15 '18 at 5:28
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
);
);
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%2fstackoverflow.com%2fquestions%2f53312485%2frandomized-quicksort-partitioning-probability%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
Let there be N elements in the array. If the picked pivot is one of the smallest [Nα] elements in the array, then the left partition's size will be less than Nα. Similarly, if the picked pivot is one of the largest [Nα] elements in the array, the right partition's size will be less than Nα.
Hence, there are N - 2 * [Nα] elements that you can pick such that both partitions have size greater than or equal to Nα. Since the algorithm picks a pivot randomly, all elements have an equal probability of getting picked.
So, the probability of getting such a split is 1 - 2α + O(1 / N).
answered Nov 15 '18 at 5:04
merlynmerlyn
1,77011323
By "pick one of the smallest Nα elements", do you mean pick that element as the pivot? Since α is not an integer,Nαmay be a fraction. Can you pick the 3.5 smallest element from an array? Please elaborate in your answer, don't respond in comments.
– Abhijit Sarkar
Nov 15 '18 at 5:08
@AbhijitSarkar You can truncate the fractional value. The difference is negligible. I have updated the answer with the same.
– merlyn
Nov 15 '18 at 5:20
I think you mean the probability is1 - 2α. Your answer1 - 2α + O(1 / N)is not one of the choices, and doesn't follow from your argument.(N - 2 * Na)/N = 1 - 2a
– Abhijit Sarkar
Nov 15 '18 at 5:24
@AbhijitSarkar That's what I meant by negligible. Some fractional part over N will be left because you can't pick 3.5 elements.
– merlyn
Nov 15 '18 at 5:28
add a comment |
Let there be N elements in the array. If the picked pivot is one of the smallest [Nα] elements in the array, then the left partition's size will be less than Nα. Similarly, if the picked pivot is one of the largest [Nα] elements in the array, the right partition's size will be less than Nα.
Hence, there are N - 2 * [Nα] elements that you can pick such that both partitions have size greater than or equal to Nα. Since the algorithm picks a pivot randomly, all elements have an equal probability of getting picked.
So, the probability of getting such a split is 1 - 2α + O(1 / N).
answered Nov 15 '18 at 5:04
merlynmerlyn
1,77011323
By "pick one of the smallest Nα elements", do you mean pick that element as the pivot? Since α is not an integer,Nαmay be a fraction. Can you pick the 3.5 smallest element from an array? Please elaborate in your answer, don't respond in comments.
– Abhijit Sarkar
Nov 15 '18 at 5:08
@AbhijitSarkar You can truncate the fractional value. The difference is negligible. I have updated the answer with the same.
– merlyn
Nov 15 '18 at 5:20
I think you mean the probability is1 - 2α. Your answer1 - 2α + O(1 / N)is not one of the choices, and doesn't follow from your argument.(N - 2 * Na)/N = 1 - 2a
– Abhijit Sarkar
Nov 15 '18 at 5:24
@AbhijitSarkar That's what I meant by negligible. Some fractional part over N will be left because you can't pick 3.5 elements.
– merlyn
Nov 15 '18 at 5:28
add a comment |
Let there be N elements in the array. If the picked pivot is one of the smallest [Nα] elements in the array, then the left partition's size will be less than Nα. Similarly, if the picked pivot is one of the largest [Nα] elements in the array, the right partition's size will be less than Nα.
Hence, there are N - 2 * [Nα] elements that you can pick such that both partitions have size greater than or equal to Nα. Since the algorithm picks a pivot randomly, all elements have an equal probability of getting picked.
So, the probability of getting such a split is 1 - 2α + O(1 / N).
answered Nov 15 '18 at 5:04
merlynmerlyn
1,77011323
Let there be N elements in the array. If the picked pivot is one of the smallest [Nα] elements in the array, then the left partition's size will be less than Nα. Similarly, if the picked pivot is one of the largest [Nα] elements in the array, the right partition's size will be less than Nα.
Hence, there are N - 2 * [Nα] elements that you can pick such that both partitions have size greater than or equal to Nα. Since the algorithm picks a pivot randomly, all elements have an equal probability of getting picked.
So, the probability of getting such a split is 1 - 2α + O(1 / N).
answered Nov 15 '18 at 5:04
merlynmerlyn
1,77011323
edited Nov 15 '18 at 5:14
answered Nov 15 '18 at 5:04
merlynmerlyn
1,77011323
answered Nov 15 '18 at 5:04
merlynmerlyn
1,77011323
answered Nov 15 '18 at 5:04
merlynmerlyn
1,77011323
1,77011323
By "pick one of the smallest Nα elements", do you mean pick that element as the pivot? Since α is not an integer,Nαmay be a fraction. Can you pick the 3.5 smallest element from an array? Please elaborate in your answer, don't respond in comments.
– Abhijit Sarkar
Nov 15 '18 at 5:08
@AbhijitSarkar You can truncate the fractional value. The difference is negligible. I have updated the answer with the same.
– merlyn
Nov 15 '18 at 5:20
I think you mean the probability is1 - 2α. Your answer1 - 2α + O(1 / N)is not one of the choices, and doesn't follow from your argument.(N - 2 * Na)/N = 1 - 2a
– Abhijit Sarkar
Nov 15 '18 at 5:24
@AbhijitSarkar That's what I meant by negligible. Some fractional part over N will be left because you can't pick 3.5 elements.
– merlyn
Nov 15 '18 at 5:28
add a comment |
By "pick one of the smallest Nα elements", do you mean pick that element as the pivot? Since α is not an integer,Nαmay be a fraction. Can you pick the 3.5 smallest element from an array? Please elaborate in your answer, don't respond in comments.
– Abhijit Sarkar
Nov 15 '18 at 5:08
@AbhijitSarkar You can truncate the fractional value. The difference is negligible. I have updated the answer with the same.
– merlyn
Nov 15 '18 at 5:20
I think you mean the probability is1 - 2α. Your answer1 - 2α + O(1 / N)is not one of the choices, and doesn't follow from your argument.(N - 2 * Na)/N = 1 - 2a
– Abhijit Sarkar
Nov 15 '18 at 5:24
@AbhijitSarkar That's what I meant by negligible. Some fractional part over N will be left because you can't pick 3.5 elements.
– merlyn
Nov 15 '18 at 5:28
By "pick one of the smallest Nα elements", do you mean pick that element as the pivot? Since α is not an integer,
Nα may be a fraction. Can you pick the 3.5 smallest element from an array? Please elaborate in your answer, don't respond in comments.– Abhijit Sarkar
Nov 15 '18 at 5:08
By "pick one of the smallest Nα elements", do you mean pick that element as the pivot? Since α is not an integer,
Nα may be a fraction. Can you pick the 3.5 smallest element from an array? Please elaborate in your answer, don't respond in comments.– Abhijit Sarkar
Nov 15 '18 at 5:08
@AbhijitSarkar You can truncate the fractional value. The difference is negligible. I have updated the answer with the same.
– merlyn
Nov 15 '18 at 5:20
@AbhijitSarkar You can truncate the fractional value. The difference is negligible. I have updated the answer with the same.
– merlyn
Nov 15 '18 at 5:20
I think you mean the probability is
1 - 2α. Your answer 1 - 2α + O(1 / N) is not one of the choices, and doesn't follow from your argument. (N - 2 * Na)/N = 1 - 2a– Abhijit Sarkar
Nov 15 '18 at 5:24
I think you mean the probability is
1 - 2α. Your answer 1 - 2α + O(1 / N) is not one of the choices, and doesn't follow from your argument. (N - 2 * Na)/N = 1 - 2a– Abhijit Sarkar
Nov 15 '18 at 5:24
@AbhijitSarkar That's what I meant by negligible. Some fractional part over N will be left because you can't pick 3.5 elements.
– merlyn
Nov 15 '18 at 5:28
@AbhijitSarkar That's what I meant by negligible. Some fractional part over N will be left because you can't pick 3.5 elements.
– merlyn
Nov 15 '18 at 5:28
add a comment |
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.
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%2fstackoverflow.com%2fquestions%2f53312485%2frandomized-quicksort-partitioning-probability%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
