Algorithm analysis - Data Structures and Problem Solving Using Java - page 213

Note in particular that we do not have definitive convergence. One prob-
lem is that the clock that we used to time the program ticks only every 10 ms.
Note also that there is not a great difference between O ( N ) and O ( N log N ) .

Certainly an O ( N log N ) algorithm is much closer to being linear than being

quadratic.

limitations of big-oh analysis

5.8

Big-Oh analysis is a very effective tool, but it does have limitations. As already
mentioned, its use is not appropriate for small amounts of input. For small
amounts of input, use the simplest algorithm. Also, for a particular algorithm, the
constant implied by the Big-Oh may be too large to be practical. For example, if
one algorithm's running time is governed by the formula and another
has a running time of 1000 N , then the first algorithm would most likely be better,
even though its growth rate is larger. Large constants can come into play when an
algorithm is excessively complex. They also come into play because our analysis
disregards constants and thus cannot differentiate between things like memory
access (which is cheap) and disk access (which typically is many thousand times
more expensive). Our analysis assumes infinite memory, but in applications
involving large data sets, lack of sufficient memory can be a severe problem.
Sometimes, even when constants and lower-order terms are considered,
the analysis is shown empirically to be an overestimate. In this case, the analy-
sis needs to be tightened (usually by a clever observation). Or the average-case

Worst-case is
sometimes uncom-
mon and can be
safely ignored. At
other times, it is
very common and
cannot be ignored.

2 N log N

figure 5.13
Empirical running time
for N binary searches
in an N -item
array

CPU Time T
(microseconds) T / N 2

N

T / N T / ( N log N )

10,000 1,000 0.1000000 0.0000100 0.0075257

20,000 2,000 0.1000000 0.0000050 0.0069990

40,000 4,400 0.1100000 0.0000027 0.0071953

80,000 9,300 0.1162500 0.0000015 0.0071373

160,000 19,600 0.1225000 0.0000008 0.0070860

320,000 41,700 0.1303125 0.0000004 0.0071257

640,000 87,700 0.1370313 0.0000002 0.0071046