Minimum depth of a leaf in a tree that corresponds to a comparison-based sorting algorithm

Question

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$?

Answer 1

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$.

Answer 2

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.