Question

Here is a lower bound proof for the comparison-based sorting problem:

  • Any comparison-based sorting algorithm can be considered to work by putting elements into their final positions one by one (Take the last time one element is put into its final position.).
  • To put the element $e$ which is the $i$-th one being put into its final position, the algorithms should know the relative ordering between $e$ and the first $n-1$ elements that are already put into their final positions. This costs at least $\Omega(\lg i)$ comparisons.
  • Therefore, the total number of comparisons is at least $$\sum_{i=1}^{n-1} \lg i = \Omega(n \lg n).$$

Is this a reasonable proof? (I am quite confused about the second step.) If so, how to formalize it more rigorously?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top