From mboxrd@z Thu Jan  1 00:00:00 1970
From: Dan Cross <cross@math.psu.edu>
Message-Id: <200106121415.KAA04177@augusta.math.psu.edu>
To: 9fans@cse.psu.edu
Subject: Re: [9fans] Re: the 'science' in computer science
In-Reply-To: <Pine.GSO.4.21.0106111803090.26443-100000@spirit>
References: <0cbd01c0f2c0$209433c0$e8b7c6d4@SOMA>
Cc: 
Date: Tue, 12 Jun 2001 10:15:33 -0400
Topicbox-Message-UUID: b5fe9c78-eac9-11e9-9e20-41e7f4b1d025

In article <Pine.GSO.4.21.0106111803090.26443-100000@spirit> you write:
>how about not being able to sort a list at better than n log n?

Ahem, uhh, I can sort in O(n) if I have auxilliary memory of size
proportional to n.  :-)

Apparantly, some guy did come up with an algorithm that runs in
better than O(n lg n) using no additional memory.  I don't have
a literature pointer, though; sorry.

	- Dan C.