Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!kayak.cis.ohio-state.edu!boniface
From: boniface@kayak.cis.ohio-state.edu (Andrew Boniface)
Newsgroups: alt.sources
Subject: Re: Sorting Algorithm
Summary: Correction to analysis.
Keywords: Sort Sorting C Source Linked-Lists Big-O
Message-ID: <83149@tut.cis.ohio-state.edu>
Date: 22 Aug 90 04:23:49 GMT
References: <wayned.0092@wddami.spoami.com> <15890@oolong.la.locus.com>
Sender: news@tut.cis.ohio-state.edu
Reply-To: Andrew Boniface <boniface@cis.ohio-state.edu>
Distribution: na
Organization: Ohio State University Computer and Information Science
Lines: 15

Big O notation refers to behavior in the limit.  In algorithm analysis
this means in the limit as input length, e.g. number of items to be
sorted, approaches infinity.  Sorting n items by `binary insertion'
into a linked list requires roughly n^2 pointer followings (if done
efficiently, otherwise more n^2*log n) and log n comparisons.  If
n*{time to follow a pointer} > log n * {time to do a comparison}
then clearly the time to follow pointers dominates.

Unless the times above vary with n, then, as n goes to infinity, the
pointer followings eventually take up most of the time, yielding
O(n^2) execution time. Big O analysis is CRUDE (it will not tell you
how big n must be for the n^2 term to take over), but it is not
ambiguous.

--Andrew W Boniface