Randomized quicksort recursion depth
I'm reading Algorithms Illuminated: Part 1, and problem 5.3 states:
Let ⍺ be some constant, independent of the input array length n,
strictly between 0 and 1/2. Assume you achieve the approximately
balanced splits from the preceding
problem in every
recursive call - so whenever a recursive call is given an array of
length k, each of its two recursive calls is passed a subarray with
length between ⍺k and (1 - ⍺)k. How many successive recursive calls
can occur before triggering the base case? Equivalently, which levels
of the algorithm’s recursion tree can contain leaves? Express your
answer as a range of possible numbers d, from the minimum to the
maximum number of recursive calls that might be needed. [Hint: The
formula that relates logarithmic functions with different bases is log
n = ln n]
Answer choices:
- -log(n)/log(⍺) <= d <= -log(n)/log(1 - ⍺)
- 0 <= d <= -log(n)/log(⍺)
- -log(n)/log(1 - ⍺) <= d <= -log(n)/log(⍺)
- -log(n)/log(1 - 2⍺) <= d <= -log(n)/log(1 - ⍺)
My analysis:
If ⍺ < 1/2, then 1 - ⍺ > ⍺, thus the branch with subarray length (1 - ⍺)n will have greater recursion depth.
n / (1 - ⍺)^d = 1
Taking log[base(1 - ⍺)] on both sides
log[base(1 - ⍺)](n) = d
By log rule
d = log(n)/log(1 - ⍺)
The best case should be log(n)/log(⍺), thus answer 1 seems to be correct. However, I'm confused by the minus signs; I don't understand how can the height of a recursion tree be negative. Also, I'd like someone to validate my analysis as shown above.
Any ideas?
algorithm recursion quicksort
asked Nov 16 '18 at 8:09
Abhijit SarkarAbhijit Sarkar
7,73474396
add a comment |
I'm reading Algorithms Illuminated: Part 1, and problem 5.3 states:
Let ⍺ be some constant, independent of the input array length n,
strictly between 0 and 1/2. Assume you achieve the approximately
balanced splits from the preceding
problem in every
recursive call - so whenever a recursive call is given an array of
length k, each of its two recursive calls is passed a subarray with
length between ⍺k and (1 - ⍺)k. How many successive recursive calls
can occur before triggering the base case? Equivalently, which levels
of the algorithm’s recursion tree can contain leaves? Express your
answer as a range of possible numbers d, from the minimum to the
maximum number of recursive calls that might be needed. [Hint: The
formula that relates logarithmic functions with different bases is log
n = ln n]
Answer choices:
- -log(n)/log(⍺) <= d <= -log(n)/log(1 - ⍺)
- 0 <= d <= -log(n)/log(⍺)
- -log(n)/log(1 - ⍺) <= d <= -log(n)/log(⍺)
- -log(n)/log(1 - 2⍺) <= d <= -log(n)/log(1 - ⍺)
My analysis:
If ⍺ < 1/2, then 1 - ⍺ > ⍺, thus the branch with subarray length (1 - ⍺)n will have greater recursion depth.
n / (1 - ⍺)^d = 1
Taking log[base(1 - ⍺)] on both sides
log[base(1 - ⍺)](n) = d
By log rule
d = log(n)/log(1 - ⍺)
The best case should be log(n)/log(⍺), thus answer 1 seems to be correct. However, I'm confused by the minus signs; I don't understand how can the height of a recursion tree be negative. Also, I'd like someone to validate my analysis as shown above.
Any ideas?
algorithm recursion quicksort
asked Nov 16 '18 at 8:09
Abhijit SarkarAbhijit Sarkar
7,73474396
add a comment |
I'm reading Algorithms Illuminated: Part 1, and problem 5.3 states:
Let ⍺ be some constant, independent of the input array length n,
strictly between 0 and 1/2. Assume you achieve the approximately
balanced splits from the preceding
problem in every
recursive call - so whenever a recursive call is given an array of
length k, each of its two recursive calls is passed a subarray with
length between ⍺k and (1 - ⍺)k. How many successive recursive calls
can occur before triggering the base case? Equivalently, which levels
of the algorithm’s recursion tree can contain leaves? Express your
answer as a range of possible numbers d, from the minimum to the
maximum number of recursive calls that might be needed. [Hint: The
formula that relates logarithmic functions with different bases is log
n = ln n]
Answer choices:
- -log(n)/log(⍺) <= d <= -log(n)/log(1 - ⍺)
- 0 <= d <= -log(n)/log(⍺)
- -log(n)/log(1 - ⍺) <= d <= -log(n)/log(⍺)
- -log(n)/log(1 - 2⍺) <= d <= -log(n)/log(1 - ⍺)
My analysis:
If ⍺ < 1/2, then 1 - ⍺ > ⍺, thus the branch with subarray length (1 - ⍺)n will have greater recursion depth.
n / (1 - ⍺)^d = 1
Taking log[base(1 - ⍺)] on both sides
log[base(1 - ⍺)](n) = d
By log rule
d = log(n)/log(1 - ⍺)
The best case should be log(n)/log(⍺), thus answer 1 seems to be correct. However, I'm confused by the minus signs; I don't understand how can the height of a recursion tree be negative. Also, I'd like someone to validate my analysis as shown above.
Any ideas?
algorithm recursion quicksort
asked Nov 16 '18 at 8:09
Abhijit SarkarAbhijit Sarkar
7,73474396
I'm reading Algorithms Illuminated: Part 1, and problem 5.3 states:
Let ⍺ be some constant, independent of the input array length n,
strictly between 0 and 1/2. Assume you achieve the approximately
balanced splits from the preceding
problem in every
recursive call - so whenever a recursive call is given an array of
length k, each of its two recursive calls is passed a subarray with
length between ⍺k and (1 - ⍺)k. How many successive recursive calls
can occur before triggering the base case? Equivalently, which levels
of the algorithm’s recursion tree can contain leaves? Express your
answer as a range of possible numbers d, from the minimum to the
maximum number of recursive calls that might be needed. [Hint: The
formula that relates logarithmic functions with different bases is log
n = ln n]
Answer choices:
- -log(n)/log(⍺) <= d <= -log(n)/log(1 - ⍺)
- 0 <= d <= -log(n)/log(⍺)
- -log(n)/log(1 - ⍺) <= d <= -log(n)/log(⍺)
- -log(n)/log(1 - 2⍺) <= d <= -log(n)/log(1 - ⍺)
My analysis:
If ⍺ < 1/2, then 1 - ⍺ > ⍺, thus the branch with subarray length (1 - ⍺)n will have greater recursion depth.
n / (1 - ⍺)^d = 1
Taking log[base(1 - ⍺)] on both sides
log[base(1 - ⍺)](n) = d
By log rule
d = log(n)/log(1 - ⍺)
The best case should be log(n)/log(⍺), thus answer 1 seems to be correct. However, I'm confused by the minus signs; I don't understand how can the height of a recursion tree be negative. Also, I'd like someone to validate my analysis as shown above.
Any ideas?
algorithm recursion quicksort
algorithm recursion quicksort
asked Nov 16 '18 at 8:09
Abhijit SarkarAbhijit Sarkar
7,73474396
asked Nov 16 '18 at 8:09
Abhijit SarkarAbhijit Sarkar
7,73474396
edited Nov 16 '18 at 9:14
Abhijit Sarkar
asked Nov 16 '18 at 8:09
Abhijit SarkarAbhijit Sarkar
7,73474396
asked Nov 16 '18 at 8:09
Abhijit SarkarAbhijit Sarkar
7,73474396
asked Nov 16 '18 at 8:09
Abhijit SarkarAbhijit Sarkar
7,73474396
7,73474396
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
Your analysis has a small bug.
The correct equation will be n * (1 - ⍺) ^ d = 1 rather than n / (1 - ⍺) ^ d = 1.
This adds the negative sign you are looking for.
Remember that both ⍺ and (1 - ⍺) are less than 1. So, there logarithms are negative. Adding one more negative symbol on that results in an overall positive value for minimum and maximum depth.
answered Nov 16 '18 at 8:58
merlynmerlyn
1,77211323
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%2f53333791%2frandomized-quicksort-recursion-depth%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
Your analysis has a small bug.
The correct equation will be n * (1 - ⍺) ^ d = 1 rather than n / (1 - ⍺) ^ d = 1.
This adds the negative sign you are looking for.
Remember that both ⍺ and (1 - ⍺) are less than 1. So, there logarithms are negative. Adding one more negative symbol on that results in an overall positive value for minimum and maximum depth.
answered Nov 16 '18 at 8:58
merlynmerlyn
1,77211323
add a comment |
Your analysis has a small bug.
The correct equation will be n * (1 - ⍺) ^ d = 1 rather than n / (1 - ⍺) ^ d = 1.
This adds the negative sign you are looking for.
Remember that both ⍺ and (1 - ⍺) are less than 1. So, there logarithms are negative. Adding one more negative symbol on that results in an overall positive value for minimum and maximum depth.
answered Nov 16 '18 at 8:58
merlynmerlyn
1,77211323
add a comment |
Your analysis has a small bug.
The correct equation will be n * (1 - ⍺) ^ d = 1 rather than n / (1 - ⍺) ^ d = 1.
This adds the negative sign you are looking for.
Remember that both ⍺ and (1 - ⍺) are less than 1. So, there logarithms are negative. Adding one more negative symbol on that results in an overall positive value for minimum and maximum depth.
answered Nov 16 '18 at 8:58
merlynmerlyn
1,77211323
Your analysis has a small bug.
The correct equation will be n * (1 - ⍺) ^ d = 1 rather than n / (1 - ⍺) ^ d = 1.
This adds the negative sign you are looking for.
Remember that both ⍺ and (1 - ⍺) are less than 1. So, there logarithms are negative. Adding one more negative symbol on that results in an overall positive value for minimum and maximum depth.
answered Nov 16 '18 at 8:58
merlynmerlyn
1,77211323
edited Nov 16 '18 at 9:04
answered Nov 16 '18 at 8:58
merlynmerlyn
1,77211323
answered Nov 16 '18 at 8:58
merlynmerlyn
1,77211323
answered Nov 16 '18 at 8:58
merlynmerlyn
1,77211323
1,77211323
add a comment |
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%2f53333791%2frandomized-quicksort-recursion-depth%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
