Java Reference
In-Depth Information
n
X
T(n) = np
n
+
(i + 1)p
i
:
i=0
What happens to the equation if we assume all the p
i
's are equal (except p
0
)?
n1
X
T(n)
= p
n
n +
(i + 1)p
i=0
n
X
= p
n
n + p
i
i=1
= p
n
n + p
n(n + 1)
2
1 p
n
n
n(n + 1)
2
= p
n
n +
n + 1 + p
n
(n 1)
2
=
Depending on the value of p
n
,
n+1
2
T(n) n.
For large collections of records that are searched repeatedly, sequential search
is unacceptably slow. One way to reduce search time is to preprocess the records
by sorting them. Given a sorted array, an obvious improvement over simple linear
search is to test if the current element in L is greater than K. If it is, then we know
that K cannot appear later in the array, and we can quit the search early. But this
still does not improve the worst-case cost of the algorithm.
We can also observe that if we look first at position 1 in sorted array L and find
that K is bigger, then we rule out position 0 as well as position 1. Because more
is often better, what if we look at position 2 in L and find that K is bigger yet?
This rules out positions 0, 1, and 2 with one comparison. What if we carry this to
the extreme and look first at the last position in L and find that K is bigger? Then
we know in one comparison that K is not in L. This is very useful to know, but
what is wrong with the conclusion that we should always start by looking at the last
position? The problem is that, while we learn a lot sometimes (in one comparison
we might learn that K is not in the list), usually we learn only a little bit (that the
last element is not K).
The question then becomes: What is the right amount to jump? This leads us
to an algorithm known as Jump Search. For some value j, we check every j'th
element in L, that is, we check elements L[j], L[2j], and so on. So long as K is
greater than the values we are checking, we continue on.
But when we reach a
