Lower sorting estimates for a small fraction of the input?

Question

Can someone let me through the math part of solving the next problem.

Show that there is no sort whose run time is linear at least half out of n! inputs of length n. What about the fraction of 1 / n inputs of length n? What about the fraction (1 / (2) ^ n)?

Decision:

If sorting is performed in linear time for m input permutations, then the height h is the part of the decision tree consisting of m corresponding leaves and their ancestors are linear. Use the same argument as in the proof of Theorem 8.1 to show that this is not possible for m = n! / 2, n! / N or n! / 2n. We have 2 ^ h ≥ m, which gives h ≥ logm. For all possible ms given here, logm = Ω (n log n), therefore h = Ω (n log n). In particular,

lgn!/2= lg n! − 1 ≥ n lg n − n lg e − 1 lgn!/n= lg n! − lg n ≥ n lg n − n lg e − lg n lgn!/2^n= lg n! − n ≥ n lg n − n lg e − n 

Answer 1

Each of these proofs is a simple modification of a more general proof that you cannot have a sort that sorts faster than & Omega; (n log n) (you can see this evidence in this earlier answer ). Intuitively, the reasoning is as follows. For the sorting algorithm to work correctly, it must be able to determine what the original order of the elements is. Otherwise, he cannot change the order of the values ​​to place them in ascending order. For n elements, there is n! different permutations of these elements, which means that there is n! various inputs to the sorting algorithm.

Initially, the algorithm does not know anything about the input sequence and cannot distinguish any of n! various permutations. Each time the algorithm performs a comparison, it gets a little more information about how the elements are ordered. In particular, it can determine if the input permutation is in the permutation group where the comparison gives true or in the permutation group where the comparison gives false. You can visualize how the algorithm works like a binary tree, where each node corresponds to a certain state of the algorithm, and (up to) two children of a particular node indicate the state of the algorithm that will be entered if the comparison gives true or false.

For the sorting algorithm to be able to sort correctly, it must be able to enter a unique state for each possible input, because otherwise the algorithm could not distinguish between two different input sequences and therefore would sort at least one of them incorrectly. This means that if you consider the number of leaf nodes in the tree (the parts where the algorithm has finished the comparison and is going to sort), there must be at least one leaf node for each input permutation. There is n in the general proof! permutations, so there must be at least n! leaf nodes. In a binary tree, the only way to have k-leaf nodes is to have a height of at least & Omega; (log k), which means you need to run at least & Omega; (log k) comparisons. Thus, the total bottom grade for sorting is & Omega; (log n!) = & Omega; (n log n) according to the Stirling approximation.

In the cases you are considering, we restrict ourselves to a subset of these possible permutations. For example, suppose we want to be able to sort n! / 2 permutations. This means that our tree must have a height of at least log (n! / 2) = log n! - 1 = & Omega; (n log n). As a result. you cannot sort O (n) in time, because no linear function grows with the speed & Omega; (n log n). In the second part, if you can get n! / N sorted by linear time, again the decision tree should have the height lg (n! / N) = log n! - log n = & Omega; (n log n), so you cannot sort in O (n) comparisons. For the final, we get that log n! / 2 ⁿ = log n! - n = & Omega; (n log n), so again it cannot be sorted in O (n) time.

However, you can sort 2 ⁿ permutations in linear time, since lg 2 ⁿ = n = O (n).

Hope this helps!