ANALYZING ALGORITHMS

If we know how long each statement takes to execute, and we know how many names are in the list, we
can calculate the time required for the algorithm to execute. However, the important thing to know about an
algorithm is usually not how long it will take to solve any particular problem. The important thing to know is
how the time taken to solve the problem will vary as the size of the problem changes.
The sequential search algorithm will take longer as the number of comparisons becomes greater. The real
work of the algorithm is in comparing each name to the search name. Most other statements in the algorithm get
executed only once, but as long as the while condition remains true, the comparisons occur again and again.
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.
Of course, for any particular search, the time required will depend on where in the list the match occurs.
If the first name is a match, then it doesn’t matter how long the list is. If the name does not occur in the list, the
search will always require comparing the search name with all the names in the list.
We say the sequential search algorithm is Θ(n) because in the average case, and the worst case, its performance
slows in proportion to n, the length of the list. Sometimes algorithms are characterized for best-case performance,
but usually average performance, and particularly worst-case performance are reported. The average case is usually
better for setting expectations, and the worst case provides a boundary upon which one can rely.