Sorting Algorithm

[Andrew Boniface]

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