Minimum depth of a leaf in a tree that corresponds to a comparison-based sorting algorithm
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{
margin-bottom:0;
}
$begingroup$
The lower bound of comparisons in a comparison-based sorting algorithm is $log_2 n!=Θ(nlog n)$. Yet there can be less comparisons needed in an algorithm.
If you take a sorted array, it will take $n-1 = O(n)$ comparisons (with insertion sort) to sort the array — comparing every adjacent pair of numbers. I don't understand then how is $log_2 n!=Θ(nlog n)$ the lower bound.
I also don't understand the corresponding trees to the sorting-based algorithms:
each leaf in the tree corresponds to one of the permutations of the $n$ numbers. If the minimum number of comparisons needed is $log_2 n!$ then the depth of every leaf should be at least $log_2 n!$, yet I saw that it's possible for a leaf to be with depth of $O(n)$.
Can there be leaves with depth even smaller than $n-1$?
sorting
$endgroup$
add a comment
|
$begingroup$
The lower bound of comparisons in a comparison-based sorting algorithm is $log_2 n!=Θ(nlog n)$. Yet there can be less comparisons needed in an algorithm.
If you take a sorted array, it will take $n-1 = O(n)$ comparisons (with insertion sort) to sort the array — comparing every adjacent pair of numbers. I don't understand then how is $log_2 n!=Θ(nlog n)$ the lower bound.
I also don't understand the corresponding trees to the sorting-based algorithms:
each leaf in the tree corresponds to one of the permutations of the $n$ numbers. If the minimum number of comparisons needed is $log_2 n!$ then the depth of every leaf should be at least $log_2 n!$, yet I saw that it's possible for a leaf to be with depth of $O(n)$.
Can there be leaves with depth even smaller than $n-1$?
sorting
$endgroup$
add a comment
|
$begingroup$
The lower bound of comparisons in a comparison-based sorting algorithm is $log_2 n!=Θ(nlog n)$. Yet there can be less comparisons needed in an algorithm.
If you take a sorted array, it will take $n-1 = O(n)$ comparisons (with insertion sort) to sort the array — comparing every adjacent pair of numbers. I don't understand then how is $log_2 n!=Θ(nlog n)$ the lower bound.
I also don't understand the corresponding trees to the sorting-based algorithms:
each leaf in the tree corresponds to one of the permutations of the $n$ numbers. If the minimum number of comparisons needed is $log_2 n!$ then the depth of every leaf should be at least $log_2 n!$, yet I saw that it's possible for a leaf to be with depth of $O(n)$.
Can there be leaves with depth even smaller than $n-1$?
sorting
$endgroup$
The lower bound of comparisons in a comparison-based sorting algorithm is $log_2 n!=Θ(nlog n)$. Yet there can be less comparisons needed in an algorithm.
If you take a sorted array, it will take $n-1 = O(n)$ comparisons (with insertion sort) to sort the array — comparing every adjacent pair of numbers. I don't understand then how is $log_2 n!=Θ(nlog n)$ the lower bound.
I also don't understand the corresponding trees to the sorting-based algorithms:
each leaf in the tree corresponds to one of the permutations of the $n$ numbers. If the minimum number of comparisons needed is $log_2 n!$ then the depth of every leaf should be at least $log_2 n!$, yet I saw that it's possible for a leaf to be with depth of $O(n)$.
Can there be leaves with depth even smaller than $n-1$?
sorting
sorting
edited May 27 at 11:11
Yuval Filmus
208k15 gold badges202 silver badges369 bronze badges
208k15 gold badges202 silver badges369 bronze badges
asked May 27 at 10:21
marianovmarianov
644 bronze badges
644 bronze badges
add a comment
|
add a comment
|
2 Answers
2
active
oldest
votes
$begingroup$
The lower bound is for the worst-case number of comparisons. Every comparison-based sorting algorithm performs $Omega(nlog n)$ comparisons in the worst case. This means that the tree has depth $Omega(nlog n)$.
If you don't like the tree argument, here is an adversary argument which is basically a reformulation of the tree argument. We will maintain the set $Pi$ of all permutations consistent with the answers so far. When the algorithm compares $i$ to $j$, we answer the result which reduces $Pi$ by at most a half (one of the two answers must have this property). After $log_2 (n!/2)$ steps there will still be at least two permutations consistent with the answers so far, hence the algorithm must make at least $log_2 n! = Omega(nlog n)$ comparisons on this branch.
In fact, we can strengthen this result (going back to the tree argument): every comparison-based sorting algorithm makes $Omega(nlog n)$ comparisons on average (when the input is a random permutation of $1,ldots,n$). For the proof, note that there can be at most $2^k$ leaves at depth $k$. In particular, the number of leaves at depth $(log n!)/2$ is at most $sqrt{n!}$. Therefore for at least $n! - sqrt{n!}$ permutations, all leaves are at depth more than $(log n!)/2$, and for this $1-o(1)$ fraction of permutations, the algorithm will make at least $(log n!)/2 = Omega(nlog n)$ comparisons.
Finally, let us show that you cannot possibly know the correct permutation if you perform less than $n-1$ comparisons. Construct a graph whose vertices are the elements of the array, and $(i,j)$ are connected if you compared the elements at these positions. If you make less than $n-1$ comparisons, then the graph won't be connected. In particular, you can partition the vertex set into two non-empty parts $A,B$ such that no element of $A$ was compared to any element of $B$. In particular, there is a permutation consistent with the performed comparisons in which all elements of $A$ are smaller than all elements of $B$, and another one in which all elements of $A$ are larger than all elements of $B$.
$endgroup$
$begingroup$
Can you please explain why does every comparison reduces Π (all the permutations consistent with the answers so far) by at most half? I have some intuition about this but I want to see an actual explanation.
$endgroup$
– marianov
May 28 at 11:52
$begingroup$
There are only two possible answers, so one of them reduces the size by at most a half.
$endgroup$
– Yuval Filmus
May 28 at 11:53
$begingroup$
Another thing: why "After log2(n!/2) steps there will still be at least two permutations consistent with the answers so far, hence the algorithm must make at least log2n!=Ω(nlogn) comparisons on this branch" ?
$endgroup$
– marianov
May 28 at 12:22
1
$begingroup$
Since $n!/2^{log_2(n!/2)} = 2$. Actually I'm cheating a bit since $log_2(n!/2)$ is usually not an integer, and so you need to consider $lfloor log_2(n!/2) rfloor$ instead.
$endgroup$
– Yuval Filmus
May 28 at 13:34
add a comment
|
$begingroup$
The worst-case time complexity of an algorithm is the time complexity for the worst-case input. Insertion sort takes $Theta(n^2)$ in the worst-case, not $O(n)$. However, mergesort and heapsort each take $Theta(n log n)$ in the worst-case, and so achieve the $Omega(n log n)$ lower bound.
Suppose $n!$ is roughly $1000$, so that $log n!$ is about $10$ (I know $1000$ is not the factorial of any integer, but just suppose you have a $1000$ permutations that need to be put as leaves). A nearly complete binary tree with $1000$ leaves will have a height of about $10$ (plus or minus 1). If the binary tree is not complete, then the height (or depth) will be larger. So, if some leaves in the binary tree are at small depth, then there exist other leaves in the tree which have a large depth, and in fact these leaves would have a larger depth than would have been the case if all leaves had the same depth. But even in the best case situation - where the tree is the shortest - there will exist leaves of height at least $10$, and so the height of the tree is always at least $10$. Similarly, if there are $n!$ leaves in a binary tree, there will exist some leaves having height at least $log n!$. Therefore, the height of a binary tree having $n!$ leaves is at least $log n!$. This part of your question is about the maximum number of nodes (or just leaves) that can be accommodated in a tree having some fixed height, and isn't related to sorting.
Now to show that there can't be any permutation at depth $n-2$. We need at least $5-1=4$ comparisons to sort five elements. To understand this intuitively, observe that if $a_i$ is the $i$th element and we know $a_1 < a_2$ and $a_2 < a_3$, then there is no need to compare $a_1$ with $a_3$ and we can sort the three elements as $(a_1,a_2,a_3)$. We can deduce how $a_1$ and $a_3$ fare (relative to each other) without making another comparison because the first and third elements are being compared indirectly (via the second element). But if there were 5 elements in the array, two comparisons are not enough to make all five elements directly or indirectly related to each other. This is because a connected graph on 5 vertices must have at least $5-1=4$ edges.
If positions 1 and 2 are compared, 2 and 3 are compared, and 4 and 5 are compared, and no further comparisons are made, then the algorithm cannot correctly sort the five elements because there is no way to determine whether the elements in ${a_1,a_2,a_3}$ are smaller than or larger than the elements in ${a_4,a_5}$ - we would only know how the elements within each subset fare relative to each other. A correct algorithm should be able to produce one of at least two different outputs, depending on whether the first subset contains large values, or whether the first subset contains all small values. Similarly, for all $n$ elements of the array to be directly or at least indirectly compared to each other, at least $n-1$ comparisons must be made.
$endgroup$
add a comment
|
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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/4.0/"u003ecc by-sa 4.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%2fcs.stackexchange.com%2fquestions%2f109917%2fminimum-depth-of-a-leaf-in-a-tree-that-corresponds-to-a-comparison-based-sorting%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The lower bound is for the worst-case number of comparisons. Every comparison-based sorting algorithm performs $Omega(nlog n)$ comparisons in the worst case. This means that the tree has depth $Omega(nlog n)$.
If you don't like the tree argument, here is an adversary argument which is basically a reformulation of the tree argument. We will maintain the set $Pi$ of all permutations consistent with the answers so far. When the algorithm compares $i$ to $j$, we answer the result which reduces $Pi$ by at most a half (one of the two answers must have this property). After $log_2 (n!/2)$ steps there will still be at least two permutations consistent with the answers so far, hence the algorithm must make at least $log_2 n! = Omega(nlog n)$ comparisons on this branch.
In fact, we can strengthen this result (going back to the tree argument): every comparison-based sorting algorithm makes $Omega(nlog n)$ comparisons on average (when the input is a random permutation of $1,ldots,n$). For the proof, note that there can be at most $2^k$ leaves at depth $k$. In particular, the number of leaves at depth $(log n!)/2$ is at most $sqrt{n!}$. Therefore for at least $n! - sqrt{n!}$ permutations, all leaves are at depth more than $(log n!)/2$, and for this $1-o(1)$ fraction of permutations, the algorithm will make at least $(log n!)/2 = Omega(nlog n)$ comparisons.
Finally, let us show that you cannot possibly know the correct permutation if you perform less than $n-1$ comparisons. Construct a graph whose vertices are the elements of the array, and $(i,j)$ are connected if you compared the elements at these positions. If you make less than $n-1$ comparisons, then the graph won't be connected. In particular, you can partition the vertex set into two non-empty parts $A,B$ such that no element of $A$ was compared to any element of $B$. In particular, there is a permutation consistent with the performed comparisons in which all elements of $A$ are smaller than all elements of $B$, and another one in which all elements of $A$ are larger than all elements of $B$.
$endgroup$
$begingroup$
Can you please explain why does every comparison reduces Π (all the permutations consistent with the answers so far) by at most half? I have some intuition about this but I want to see an actual explanation.
$endgroup$
– marianov
May 28 at 11:52
$begingroup$
There are only two possible answers, so one of them reduces the size by at most a half.
$endgroup$
– Yuval Filmus
May 28 at 11:53
$begingroup$
Another thing: why "After log2(n!/2) steps there will still be at least two permutations consistent with the answers so far, hence the algorithm must make at least log2n!=Ω(nlogn) comparisons on this branch" ?
$endgroup$
– marianov
May 28 at 12:22
1
$begingroup$
Since $n!/2^{log_2(n!/2)} = 2$. Actually I'm cheating a bit since $log_2(n!/2)$ is usually not an integer, and so you need to consider $lfloor log_2(n!/2) rfloor$ instead.
$endgroup$
– Yuval Filmus
May 28 at 13:34
add a comment
|
$begingroup$
The lower bound is for the worst-case number of comparisons. Every comparison-based sorting algorithm performs $Omega(nlog n)$ comparisons in the worst case. This means that the tree has depth $Omega(nlog n)$.
If you don't like the tree argument, here is an adversary argument which is basically a reformulation of the tree argument. We will maintain the set $Pi$ of all permutations consistent with the answers so far. When the algorithm compares $i$ to $j$, we answer the result which reduces $Pi$ by at most a half (one of the two answers must have this property). After $log_2 (n!/2)$ steps there will still be at least two permutations consistent with the answers so far, hence the algorithm must make at least $log_2 n! = Omega(nlog n)$ comparisons on this branch.
In fact, we can strengthen this result (going back to the tree argument): every comparison-based sorting algorithm makes $Omega(nlog n)$ comparisons on average (when the input is a random permutation of $1,ldots,n$). For the proof, note that there can be at most $2^k$ leaves at depth $k$. In particular, the number of leaves at depth $(log n!)/2$ is at most $sqrt{n!}$. Therefore for at least $n! - sqrt{n!}$ permutations, all leaves are at depth more than $(log n!)/2$, and for this $1-o(1)$ fraction of permutations, the algorithm will make at least $(log n!)/2 = Omega(nlog n)$ comparisons.
Finally, let us show that you cannot possibly know the correct permutation if you perform less than $n-1$ comparisons. Construct a graph whose vertices are the elements of the array, and $(i,j)$ are connected if you compared the elements at these positions. If you make less than $n-1$ comparisons, then the graph won't be connected. In particular, you can partition the vertex set into two non-empty parts $A,B$ such that no element of $A$ was compared to any element of $B$. In particular, there is a permutation consistent with the performed comparisons in which all elements of $A$ are smaller than all elements of $B$, and another one in which all elements of $A$ are larger than all elements of $B$.
$endgroup$
$begingroup$
Can you please explain why does every comparison reduces Π (all the permutations consistent with the answers so far) by at most half? I have some intuition about this but I want to see an actual explanation.
$endgroup$
– marianov
May 28 at 11:52
$begingroup$
There are only two possible answers, so one of them reduces the size by at most a half.
$endgroup$
– Yuval Filmus
May 28 at 11:53
$begingroup$
Another thing: why "After log2(n!/2) steps there will still be at least two permutations consistent with the answers so far, hence the algorithm must make at least log2n!=Ω(nlogn) comparisons on this branch" ?
$endgroup$
– marianov
May 28 at 12:22
1
$begingroup$
Since $n!/2^{log_2(n!/2)} = 2$. Actually I'm cheating a bit since $log_2(n!/2)$ is usually not an integer, and so you need to consider $lfloor log_2(n!/2) rfloor$ instead.
$endgroup$
– Yuval Filmus
May 28 at 13:34
add a comment
|
$begingroup$
The lower bound is for the worst-case number of comparisons. Every comparison-based sorting algorithm performs $Omega(nlog n)$ comparisons in the worst case. This means that the tree has depth $Omega(nlog n)$.
If you don't like the tree argument, here is an adversary argument which is basically a reformulation of the tree argument. We will maintain the set $Pi$ of all permutations consistent with the answers so far. When the algorithm compares $i$ to $j$, we answer the result which reduces $Pi$ by at most a half (one of the two answers must have this property). After $log_2 (n!/2)$ steps there will still be at least two permutations consistent with the answers so far, hence the algorithm must make at least $log_2 n! = Omega(nlog n)$ comparisons on this branch.
In fact, we can strengthen this result (going back to the tree argument): every comparison-based sorting algorithm makes $Omega(nlog n)$ comparisons on average (when the input is a random permutation of $1,ldots,n$). For the proof, note that there can be at most $2^k$ leaves at depth $k$. In particular, the number of leaves at depth $(log n!)/2$ is at most $sqrt{n!}$. Therefore for at least $n! - sqrt{n!}$ permutations, all leaves are at depth more than $(log n!)/2$, and for this $1-o(1)$ fraction of permutations, the algorithm will make at least $(log n!)/2 = Omega(nlog n)$ comparisons.
Finally, let us show that you cannot possibly know the correct permutation if you perform less than $n-1$ comparisons. Construct a graph whose vertices are the elements of the array, and $(i,j)$ are connected if you compared the elements at these positions. If you make less than $n-1$ comparisons, then the graph won't be connected. In particular, you can partition the vertex set into two non-empty parts $A,B$ such that no element of $A$ was compared to any element of $B$. In particular, there is a permutation consistent with the performed comparisons in which all elements of $A$ are smaller than all elements of $B$, and another one in which all elements of $A$ are larger than all elements of $B$.
$endgroup$
The lower bound is for the worst-case number of comparisons. Every comparison-based sorting algorithm performs $Omega(nlog n)$ comparisons in the worst case. This means that the tree has depth $Omega(nlog n)$.
If you don't like the tree argument, here is an adversary argument which is basically a reformulation of the tree argument. We will maintain the set $Pi$ of all permutations consistent with the answers so far. When the algorithm compares $i$ to $j$, we answer the result which reduces $Pi$ by at most a half (one of the two answers must have this property). After $log_2 (n!/2)$ steps there will still be at least two permutations consistent with the answers so far, hence the algorithm must make at least $log_2 n! = Omega(nlog n)$ comparisons on this branch.
In fact, we can strengthen this result (going back to the tree argument): every comparison-based sorting algorithm makes $Omega(nlog n)$ comparisons on average (when the input is a random permutation of $1,ldots,n$). For the proof, note that there can be at most $2^k$ leaves at depth $k$. In particular, the number of leaves at depth $(log n!)/2$ is at most $sqrt{n!}$. Therefore for at least $n! - sqrt{n!}$ permutations, all leaves are at depth more than $(log n!)/2$, and for this $1-o(1)$ fraction of permutations, the algorithm will make at least $(log n!)/2 = Omega(nlog n)$ comparisons.
Finally, let us show that you cannot possibly know the correct permutation if you perform less than $n-1$ comparisons. Construct a graph whose vertices are the elements of the array, and $(i,j)$ are connected if you compared the elements at these positions. If you make less than $n-1$ comparisons, then the graph won't be connected. In particular, you can partition the vertex set into two non-empty parts $A,B$ such that no element of $A$ was compared to any element of $B$. In particular, there is a permutation consistent with the performed comparisons in which all elements of $A$ are smaller than all elements of $B$, and another one in which all elements of $A$ are larger than all elements of $B$.
answered May 27 at 11:20
Yuval FilmusYuval Filmus
208k15 gold badges202 silver badges369 bronze badges
208k15 gold badges202 silver badges369 bronze badges
$begingroup$
Can you please explain why does every comparison reduces Π (all the permutations consistent with the answers so far) by at most half? I have some intuition about this but I want to see an actual explanation.
$endgroup$
– marianov
May 28 at 11:52
$begingroup$
There are only two possible answers, so one of them reduces the size by at most a half.
$endgroup$
– Yuval Filmus
May 28 at 11:53
$begingroup$
Another thing: why "After log2(n!/2) steps there will still be at least two permutations consistent with the answers so far, hence the algorithm must make at least log2n!=Ω(nlogn) comparisons on this branch" ?
$endgroup$
– marianov
May 28 at 12:22
1
$begingroup$
Since $n!/2^{log_2(n!/2)} = 2$. Actually I'm cheating a bit since $log_2(n!/2)$ is usually not an integer, and so you need to consider $lfloor log_2(n!/2) rfloor$ instead.
$endgroup$
– Yuval Filmus
May 28 at 13:34
add a comment
|
$begingroup$
Can you please explain why does every comparison reduces Π (all the permutations consistent with the answers so far) by at most half? I have some intuition about this but I want to see an actual explanation.
$endgroup$
– marianov
May 28 at 11:52
$begingroup$
There are only two possible answers, so one of them reduces the size by at most a half.
$endgroup$
– Yuval Filmus
May 28 at 11:53
$begingroup$
Another thing: why "After log2(n!/2) steps there will still be at least two permutations consistent with the answers so far, hence the algorithm must make at least log2n!=Ω(nlogn) comparisons on this branch" ?
$endgroup$
– marianov
May 28 at 12:22
1
$begingroup$
Since $n!/2^{log_2(n!/2)} = 2$. Actually I'm cheating a bit since $log_2(n!/2)$ is usually not an integer, and so you need to consider $lfloor log_2(n!/2) rfloor$ instead.
$endgroup$
– Yuval Filmus
May 28 at 13:34
$begingroup$
Can you please explain why does every comparison reduces Π (all the permutations consistent with the answers so far) by at most half? I have some intuition about this but I want to see an actual explanation.
$endgroup$
– marianov
May 28 at 11:52
$begingroup$
Can you please explain why does every comparison reduces Π (all the permutations consistent with the answers so far) by at most half? I have some intuition about this but I want to see an actual explanation.
$endgroup$
– marianov
May 28 at 11:52
$begingroup$
There are only two possible answers, so one of them reduces the size by at most a half.
$endgroup$
– Yuval Filmus
May 28 at 11:53
$begingroup$
There are only two possible answers, so one of them reduces the size by at most a half.
$endgroup$
– Yuval Filmus
May 28 at 11:53
$begingroup$
Another thing: why "After log2(n!/2) steps there will still be at least two permutations consistent with the answers so far, hence the algorithm must make at least log2n!=Ω(nlogn) comparisons on this branch" ?
$endgroup$
– marianov
May 28 at 12:22
$begingroup$
Another thing: why "After log2(n!/2) steps there will still be at least two permutations consistent with the answers so far, hence the algorithm must make at least log2n!=Ω(nlogn) comparisons on this branch" ?
$endgroup$
– marianov
May 28 at 12:22
1
1
$begingroup$
Since $n!/2^{log_2(n!/2)} = 2$. Actually I'm cheating a bit since $log_2(n!/2)$ is usually not an integer, and so you need to consider $lfloor log_2(n!/2) rfloor$ instead.
$endgroup$
– Yuval Filmus
May 28 at 13:34
$begingroup$
Since $n!/2^{log_2(n!/2)} = 2$. Actually I'm cheating a bit since $log_2(n!/2)$ is usually not an integer, and so you need to consider $lfloor log_2(n!/2) rfloor$ instead.
$endgroup$
– Yuval Filmus
May 28 at 13:34
add a comment
|
$begingroup$
The worst-case time complexity of an algorithm is the time complexity for the worst-case input. Insertion sort takes $Theta(n^2)$ in the worst-case, not $O(n)$. However, mergesort and heapsort each take $Theta(n log n)$ in the worst-case, and so achieve the $Omega(n log n)$ lower bound.
Suppose $n!$ is roughly $1000$, so that $log n!$ is about $10$ (I know $1000$ is not the factorial of any integer, but just suppose you have a $1000$ permutations that need to be put as leaves). A nearly complete binary tree with $1000$ leaves will have a height of about $10$ (plus or minus 1). If the binary tree is not complete, then the height (or depth) will be larger. So, if some leaves in the binary tree are at small depth, then there exist other leaves in the tree which have a large depth, and in fact these leaves would have a larger depth than would have been the case if all leaves had the same depth. But even in the best case situation - where the tree is the shortest - there will exist leaves of height at least $10$, and so the height of the tree is always at least $10$. Similarly, if there are $n!$ leaves in a binary tree, there will exist some leaves having height at least $log n!$. Therefore, the height of a binary tree having $n!$ leaves is at least $log n!$. This part of your question is about the maximum number of nodes (or just leaves) that can be accommodated in a tree having some fixed height, and isn't related to sorting.
Now to show that there can't be any permutation at depth $n-2$. We need at least $5-1=4$ comparisons to sort five elements. To understand this intuitively, observe that if $a_i$ is the $i$th element and we know $a_1 < a_2$ and $a_2 < a_3$, then there is no need to compare $a_1$ with $a_3$ and we can sort the three elements as $(a_1,a_2,a_3)$. We can deduce how $a_1$ and $a_3$ fare (relative to each other) without making another comparison because the first and third elements are being compared indirectly (via the second element). But if there were 5 elements in the array, two comparisons are not enough to make all five elements directly or indirectly related to each other. This is because a connected graph on 5 vertices must have at least $5-1=4$ edges.
If positions 1 and 2 are compared, 2 and 3 are compared, and 4 and 5 are compared, and no further comparisons are made, then the algorithm cannot correctly sort the five elements because there is no way to determine whether the elements in ${a_1,a_2,a_3}$ are smaller than or larger than the elements in ${a_4,a_5}$ - we would only know how the elements within each subset fare relative to each other. A correct algorithm should be able to produce one of at least two different outputs, depending on whether the first subset contains large values, or whether the first subset contains all small values. Similarly, for all $n$ elements of the array to be directly or at least indirectly compared to each other, at least $n-1$ comparisons must be made.
$endgroup$
add a comment
|
$begingroup$
The worst-case time complexity of an algorithm is the time complexity for the worst-case input. Insertion sort takes $Theta(n^2)$ in the worst-case, not $O(n)$. However, mergesort and heapsort each take $Theta(n log n)$ in the worst-case, and so achieve the $Omega(n log n)$ lower bound.
Suppose $n!$ is roughly $1000$, so that $log n!$ is about $10$ (I know $1000$ is not the factorial of any integer, but just suppose you have a $1000$ permutations that need to be put as leaves). A nearly complete binary tree with $1000$ leaves will have a height of about $10$ (plus or minus 1). If the binary tree is not complete, then the height (or depth) will be larger. So, if some leaves in the binary tree are at small depth, then there exist other leaves in the tree which have a large depth, and in fact these leaves would have a larger depth than would have been the case if all leaves had the same depth. But even in the best case situation - where the tree is the shortest - there will exist leaves of height at least $10$, and so the height of the tree is always at least $10$. Similarly, if there are $n!$ leaves in a binary tree, there will exist some leaves having height at least $log n!$. Therefore, the height of a binary tree having $n!$ leaves is at least $log n!$. This part of your question is about the maximum number of nodes (or just leaves) that can be accommodated in a tree having some fixed height, and isn't related to sorting.
Now to show that there can't be any permutation at depth $n-2$. We need at least $5-1=4$ comparisons to sort five elements. To understand this intuitively, observe that if $a_i$ is the $i$th element and we know $a_1 < a_2$ and $a_2 < a_3$, then there is no need to compare $a_1$ with $a_3$ and we can sort the three elements as $(a_1,a_2,a_3)$. We can deduce how $a_1$ and $a_3$ fare (relative to each other) without making another comparison because the first and third elements are being compared indirectly (via the second element). But if there were 5 elements in the array, two comparisons are not enough to make all five elements directly or indirectly related to each other. This is because a connected graph on 5 vertices must have at least $5-1=4$ edges.
If positions 1 and 2 are compared, 2 and 3 are compared, and 4 and 5 are compared, and no further comparisons are made, then the algorithm cannot correctly sort the five elements because there is no way to determine whether the elements in ${a_1,a_2,a_3}$ are smaller than or larger than the elements in ${a_4,a_5}$ - we would only know how the elements within each subset fare relative to each other. A correct algorithm should be able to produce one of at least two different outputs, depending on whether the first subset contains large values, or whether the first subset contains all small values. Similarly, for all $n$ elements of the array to be directly or at least indirectly compared to each other, at least $n-1$ comparisons must be made.
$endgroup$
add a comment
|
$begingroup$
The worst-case time complexity of an algorithm is the time complexity for the worst-case input. Insertion sort takes $Theta(n^2)$ in the worst-case, not $O(n)$. However, mergesort and heapsort each take $Theta(n log n)$ in the worst-case, and so achieve the $Omega(n log n)$ lower bound.
Suppose $n!$ is roughly $1000$, so that $log n!$ is about $10$ (I know $1000$ is not the factorial of any integer, but just suppose you have a $1000$ permutations that need to be put as leaves). A nearly complete binary tree with $1000$ leaves will have a height of about $10$ (plus or minus 1). If the binary tree is not complete, then the height (or depth) will be larger. So, if some leaves in the binary tree are at small depth, then there exist other leaves in the tree which have a large depth, and in fact these leaves would have a larger depth than would have been the case if all leaves had the same depth. But even in the best case situation - where the tree is the shortest - there will exist leaves of height at least $10$, and so the height of the tree is always at least $10$. Similarly, if there are $n!$ leaves in a binary tree, there will exist some leaves having height at least $log n!$. Therefore, the height of a binary tree having $n!$ leaves is at least $log n!$. This part of your question is about the maximum number of nodes (or just leaves) that can be accommodated in a tree having some fixed height, and isn't related to sorting.
Now to show that there can't be any permutation at depth $n-2$. We need at least $5-1=4$ comparisons to sort five elements. To understand this intuitively, observe that if $a_i$ is the $i$th element and we know $a_1 < a_2$ and $a_2 < a_3$, then there is no need to compare $a_1$ with $a_3$ and we can sort the three elements as $(a_1,a_2,a_3)$. We can deduce how $a_1$ and $a_3$ fare (relative to each other) without making another comparison because the first and third elements are being compared indirectly (via the second element). But if there were 5 elements in the array, two comparisons are not enough to make all five elements directly or indirectly related to each other. This is because a connected graph on 5 vertices must have at least $5-1=4$ edges.
If positions 1 and 2 are compared, 2 and 3 are compared, and 4 and 5 are compared, and no further comparisons are made, then the algorithm cannot correctly sort the five elements because there is no way to determine whether the elements in ${a_1,a_2,a_3}$ are smaller than or larger than the elements in ${a_4,a_5}$ - we would only know how the elements within each subset fare relative to each other. A correct algorithm should be able to produce one of at least two different outputs, depending on whether the first subset contains large values, or whether the first subset contains all small values. Similarly, for all $n$ elements of the array to be directly or at least indirectly compared to each other, at least $n-1$ comparisons must be made.
$endgroup$
The worst-case time complexity of an algorithm is the time complexity for the worst-case input. Insertion sort takes $Theta(n^2)$ in the worst-case, not $O(n)$. However, mergesort and heapsort each take $Theta(n log n)$ in the worst-case, and so achieve the $Omega(n log n)$ lower bound.
Suppose $n!$ is roughly $1000$, so that $log n!$ is about $10$ (I know $1000$ is not the factorial of any integer, but just suppose you have a $1000$ permutations that need to be put as leaves). A nearly complete binary tree with $1000$ leaves will have a height of about $10$ (plus or minus 1). If the binary tree is not complete, then the height (or depth) will be larger. So, if some leaves in the binary tree are at small depth, then there exist other leaves in the tree which have a large depth, and in fact these leaves would have a larger depth than would have been the case if all leaves had the same depth. But even in the best case situation - where the tree is the shortest - there will exist leaves of height at least $10$, and so the height of the tree is always at least $10$. Similarly, if there are $n!$ leaves in a binary tree, there will exist some leaves having height at least $log n!$. Therefore, the height of a binary tree having $n!$ leaves is at least $log n!$. This part of your question is about the maximum number of nodes (or just leaves) that can be accommodated in a tree having some fixed height, and isn't related to sorting.
Now to show that there can't be any permutation at depth $n-2$. We need at least $5-1=4$ comparisons to sort five elements. To understand this intuitively, observe that if $a_i$ is the $i$th element and we know $a_1 < a_2$ and $a_2 < a_3$, then there is no need to compare $a_1$ with $a_3$ and we can sort the three elements as $(a_1,a_2,a_3)$. We can deduce how $a_1$ and $a_3$ fare (relative to each other) without making another comparison because the first and third elements are being compared indirectly (via the second element). But if there were 5 elements in the array, two comparisons are not enough to make all five elements directly or indirectly related to each other. This is because a connected graph on 5 vertices must have at least $5-1=4$ edges.
If positions 1 and 2 are compared, 2 and 3 are compared, and 4 and 5 are compared, and no further comparisons are made, then the algorithm cannot correctly sort the five elements because there is no way to determine whether the elements in ${a_1,a_2,a_3}$ are smaller than or larger than the elements in ${a_4,a_5}$ - we would only know how the elements within each subset fare relative to each other. A correct algorithm should be able to produce one of at least two different outputs, depending on whether the first subset contains large values, or whether the first subset contains all small values. Similarly, for all $n$ elements of the array to be directly or at least indirectly compared to each other, at least $n-1$ comparisons must be made.
edited May 27 at 16:10
answered May 27 at 15:27
mo2019mo2019
3165 bronze badges
3165 bronze badges
add a comment
|
add a comment
|
Thanks for contributing an answer to Computer Science 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%2fcs.stackexchange.com%2fquestions%2f109917%2fminimum-depth-of-a-leaf-in-a-tree-that-corresponds-to-a-comparison-based-sorting%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