viff
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 diff
1.1 --- a/apps/sort.py Fri Aug 08 10:54:43 2008 +0200 1.2 +++ b/apps/sort.py Fri Aug 08 13:46:41 2008 +0200 1.3 @@ -24,7 +24,7 @@ 1.4 # stages and each stage consists of n/2 parallel comparisons. The 1.5 # total number of comparisons is thus in O(n log^2 n). 1.6 # 1.7 -# This is larger than the lower bound of O(n log n) for comparison 1.8 +# This is larger than the lower bound of Omega(n log n) for comparison 1.9 # based sorting algorithms, achieved by mergesort and other well known 1.10 # algorithms. The problem with mergesort is its merging step: to merge 1.11 # two sorted arrays of length n/2 one needs up to n comparisons, and