Mercurial > mkeller
changeset 881:82ff7bfd8b64
Corrected lower bound.
Thanks to Thomas MÃ¸lhave for noticing!
author | Martin Geisler <mg@daimi.au.dk> |
---|---|
date | Fri, 08 Aug 2008 13:46:41 +0200 |
parents | 25d1109d5b60 |
children | 794a38489a2d |
files | apps/sort.py |
diffstat | 1 files changed, 1 insertions(+), 1 deletions(-) [+] |
line wrap: on
line diff
--- a/apps/sort.py Fri Aug 08 10:54:43 2008 +0200 +++ b/apps/sort.py Fri Aug 08 13:46:41 2008 +0200 @@ -24,7 +24,7 @@ # stages and each stage consists of n/2 parallel comparisons. The # total number of comparisons is thus in O(n log^2 n). # -# This is larger than the lower bound of O(n log n) for comparison +# This is larger than the lower bound of Omega(n log n) for comparison # based sorting algorithms, achieved by mergesort and other well known # algorithms. The problem with mergesort is its merging step: to merge # two sorted arrays of length n/2 one needs up to n comparisons, and