patternMinor
Minimum depth of a leaf in a tree that corresponds to a comparison-based sorting algorithm
Viewed 0 times
depthsortingminimumcomparisonalgorithmleafcorrespondsthatbasedtree
Problem
The lower bound of comparisons in a comparison-based sorting algorithm is $\log_2 n!=Θ(n\log 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!=Θ(n\log 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$?
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!=Θ(n\log 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$?
Solution
The lower bound is for the worst-case number of comparisons. Every comparison-based sorting algorithm performs $\Omega(n\log n)$ comparisons in the worst case. This means that the tree has depth $\Omega(n\log 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(n\log 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(n\log 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(n\log 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$.
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(n\log 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(n\log 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(n\log 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$.
Context
StackExchange Computer Science Q#109917, answer score: 2
Revisions (0)
No revisions yet.