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