2.1 SEQUENTIAL SEARCH 45- What about the third?
- What about the last or Nth location?
If you looked at the algorithm carefully, you should have determined that the
answers to these questions are 1, 2, 3, and N, respectively. This means that for
each of our N cases, the number of comparisons is the same as the location
where the match occurs. This gives the following equation for this average
case:^1
If we include the possibility that the target is not in the list, we will find that
there are now N + 1 possibilities. As we have seen, the case where the target is
not in the list will take N comparisons. If we assume that all N + 1 possibilities
are equally likely, we wind up with the following:
We see that including the possibility of the target not being in the list only
increases the average case by 1/2. When we consider this amount relative to
the size of the list, which could be very large, this 1/2 is not significant.
(^1) See Section 1.2.1 on average case if this first equation looks unfamiliar.
AN()^1
N
---- i
i=1
N
= ∑
AN()= N----^1 NN-----------------------() 2 +^1 by Equation 1.15
AN()= N------------- 2 +^1
AN() N-------------^1 + 1 i
i=1
N
∑
= +N
AN() N-------------^1 + 1 i
i=1
N
∑
1
N-------------+ 1 N
= +
AN()= N-------------^1 + 1 -----------------------NN() 2 +^1 +N-------------N+ 1
AN()==N---- 2 +N-------------N+ 1 N---- 2 + 1 – N-------------^1 + 1
AN()≈-------------N 2 +^2 (AsN gets very large, N-------------^1 + 1 becomes almost 0.)