For a comparison-based sort of an array of n elements, what is the best theoretical lower...

The information-theoretic lower bound for comparison-based sorting is Ω(n log n), proven via decision tree analysis. Any comparison-based sort must perform at least n log n comparisons in the worst case because there are n! possible permutations to distinguish, requiring log₂(n!) ≈ n log n bits of information. Algorithms like merge sort and heap sort achieve this bound, proving it is tight.

Step-by-step Derivation:
Information-theoretic argument: (1) There are n! possible permutations of n elements. (2) Each comparison can yield only 2 outcomes (true/false), so a decision tree of depth d can distinguish at most 2^d cases. (3) We need 2^d ≥ n!, so d ≥ log₂(n!) = log₂(n × (n-1) × ... × 1) ≈ n log₂(n) using Stirling's approximation. (4) Therefore, any comparison-based sort requires Ω(n log n) comparisons in the worst case. Option B (O(n)) is impossible because you cannot even examine all elements without at least n operations. Option C (O(log n)) is far too optimistic. Option D is a pessimistic upper bound but not the theoretical lower bound.