Java Reference
In-Depth Information
It is not always practical to reduce an algorithm's growth rate. There is a “prac-
ticality window” for every problem, in that we have a practical limit to how big an
input we wish to solve for. If our problem size never grows too big, it might not
matter if we can reduce the cost by an extra log factor, because the constant factors
in the two algorithms might differ by more than the log of the log of the input size.
For our two algorithms, let us look further and check the actual number of
comparisons used. For binary search, we need about log n 1 total comparisons.
Quadratic binary search requires about 2:4 lg lg n comparisons. If we incorporate
this observation into our table, we get a different picture about the relative differ-
ences.
Factor
n
lg n 1
2:4 lg lg n Dierence
16
3
4:8
worse
256
7
7:2
same
64K 15
9:6
1:6
2
32
31
12
2:6
But we still are not done. This is only a count of raw comparisons. Bi-
nary search is inherently much simpler than QBS, because binary search only
needs to calculate the midpoint position of the array before each comparison, while
quadratic binary search must calculate an interpolation point which is more expen-
sive. So the constant factors for QBS are even higher.
Not only are the constant factors worse on average, but QBS is far more depen-
dent than binary search on good data distribution to perform well. For example,
imagine that you are searching a telephone directory for the name “Young.” Nor-
mally you would look near the back of the topic. If you found a name beginning
with 'Z,' you might look just a little ways toward the front. If the next name you
find also begins with 'Z,' you would look a little further toward the front. If this
particular telephone directory were unusual in that half of the entries begin with 'Z,'
then you would need to move toward the front many times, each time eliminating
relatively few records from the search. In the extreme, the performance of interpo-
lation search might not be much better than sequential search if the distribution of
key values is badly calculated.
While it turns out that QBS is not a practical algorithm, this is not a typical
situation. Fortunately, algorithm growth rates are usually well behaved, so that as-
ymptotic algorithm analysis nearly always gives us a practical indication for which
of two algorithms is better.
9.2
Self-Organizing Lists
While ordering of lists is most commonly done by key value, this is not the only
viable option. Another approach to organizing lists to speed search is to order the
