If the name we are searching for is in the list, on average the algorithm will have to look at half the names
on the list before finding a match. If the name we are searching for is not on the list, the algorithm will have to
look at all the names on the list.
If the list is twice as long, approximately twice as many comparisons will be necessary. If the list is a million
times as long, approximately a million times as many comparisons will be necessary. In that case, the time devoted
to the statements executed only once will become insignificant with respect to the execution time overall. The
running time of the sequential search algorithm grows in proportion to the size of the list being searched.
We say that the ???order of growth??? of the sequential search algorithm is n. The notation for this is T(n). We
also say that an algorithm whose order of growth is within some constant factor of T(n) has a theta of NL say.
???The sequential search has a theta of n.??? The size of the problem is n, the length of the list being searched. Since
for large problems the one-time-only or a-few-times-only statements make little difference, we ignore those
constant or nearly constant times and simply focus on the fact that the running time will grow in proportion to
the length of the list being searched.
Pages:
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54