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