Path: utzoo!utgpu!watserv1!watmath!att!att!linac!pacific.mps.ohio-state.edu!zaphod.mps.ohio-state.edu!samsung!munnari.oz.au!uniwa!vax7!tkessells01
From: Kessells_SR@cc.curtin.edu.au
Newsgroups: comp.theory
Subject: Bounds for sorting algorithms
Message-ID: <4367.27357b55@cc.curtin.edu.au>
Date: 5 Nov 90 06:46:45 GMT
Organization: Curtin University of Technology
Lines: 20

Hi,

	Can someone please tell me where I can find a proof for the
fact that sorting has a lower bound of OMEGA(n log n).
Has it been proven? Who was the first to prove this? 

						Thanks in advance

						Paul Vowles

						Computing Science Department
						Curtin University of Technology
						Western Australia

-------------------------------------------------------------------------------
 Internet:	TKESSELLS01@cc.curtin.edu.au
 ACSnet:	TKESSELLS01@cc.cut.oz.au
 Bitnet:	TKESSELLS01%cc.curtin.edu.au@cunyvm.bitnet
 UUCP:		uunet!munnari.oz!cc.curtin.edu.au!TKESSELLS01
-------------------------------------------------------------------------------