Section 3.3 Analysis of Algorithms
205
The sequential search algorithm does the maximum amount of work (number
of comparisons) when x is the last item in the list or when x does not appear in
the list at all. In either case, all elements are compared to x, so n comparisons are
done. This is the “worst case” for this algorithm, and the work depends on the size
n of the input (the length of the list). The minimum amount of work is done when
x is the very first item in the list; only one comparison is made. This is the “best
case” for this algorithm. (In the algorithm of Example 27, the same number of
arithmetic operations is always done; there is no best or worst case.)
There are many possibilities between the best case and the worst case. If x falls
in the exact middle of the list, the search would require roughly n/2 comparisons.
It would be helpful to obtain some measure of the “average” amount of work done.
This measure would require some way to describe the average list being searched
and the average relationship of a target item x to that list. Exercises 35 and 36
in this section explore some aspects of average case analysis for the sequential
search algorithm. For most algorithms, however, average behavior is very difficult
to determine. To compare the efficiency of algorithms, therefore, we often content
ourselves with the worst-case count of the number of operations required.
example 28
Given a long string of text characters, can we find the first instance of a particular
substring or “pattern” within the text? This problem has a number of important
applications, such as
• looking for specific strings in an HTML document that might be governed
by a style rule of a Cascading Style Sheet.
• using the UNIX grep command to search a file for a specified string, or the
“Find” command in any text editor or word processor.
• looking for specific gene sequences within a strand of DNA.
DNA is a long molecule that is basically a chemically bonded chain of smaller
molecules called nucleotides. There are four nucleotides, abbreviated as A, C, G,
and T. Thus a section of DNA might be represented as the sequence
…TAATCATGGTCATAGCTGTTTCCTGTGTGAAATTG…
DNA is stored within the cells of living organisms on chromosomes; various
sections of these chromosomes are identified as genes. Genes, through their
DNA “instructions,” create proteins that control specific functions or traits within the organism (hair color, blood type, and so on). Thus our entire genetic code
requires only four symbols! “Mapping the human genome”, that is, determining
the entire DNA sequence of humans, was a huge scientific undertaking, essentially completed in 2003, although the work of identifying specific genes and
their particular function is ongoing. It is known, for example, that the disease
cystic fibrosis is caused by a mutation in a particular gene (DNA sequence) that
is composed of about 230,000 nucleotides.
The most intuitive (although not the most efficient) string pattern-matching
algorithm compares the pattern (a string of length m) against the text (a string of
length n with n ≥ m), starting with the first character of the text and marching
through the pattern.
205
The sequential search algorithm does the maximum amount of work (number
of comparisons) when x is the last item in the list or when x does not appear in
the list at all. In either case, all elements are compared to x, so n comparisons are
done. This is the “worst case” for this algorithm, and the work depends on the size
n of the input (the length of the list). The minimum amount of work is done when
x is the very first item in the list; only one comparison is made. This is the “best
case” for this algorithm. (In the algorithm of Example 27, the same number of
arithmetic operations is always done; there is no best or worst case.)
There are many possibilities between the best case and the worst case. If x falls
in the exact middle of the list, the search would require roughly n/2 comparisons.
It would be helpful to obtain some measure of the “average” amount of work done.
This measure would require some way to describe the average list being searched
and the average relationship of a target item x to that list. Exercises 35 and 36
in this section explore some aspects of average case analysis for the sequential
search algorithm. For most algorithms, however, average behavior is very difficult
to determine. To compare the efficiency of algorithms, therefore, we often content
ourselves with the worst-case count of the number of operations required.
example 28
Given a long string of text characters, can we find the first instance of a particular
substring or “pattern” within the text? This problem has a number of important
applications, such as
• looking for specific strings in an HTML document that might be governed
by a style rule of a Cascading Style Sheet.
• using the UNIX grep command to search a file for a specified string, or the
“Find” command in any text editor or word processor.
• looking for specific gene sequences within a strand of DNA.
DNA is a long molecule that is basically a chemically bonded chain of smaller
molecules called nucleotides. There are four nucleotides, abbreviated as A, C, G,
and T. Thus a section of DNA might be represented as the sequence
…TAATCATGGTCATAGCTGTTTCCTGTGTGAAATTG…
DNA is stored within the cells of living organisms on chromosomes; various
sections of these chromosomes are identified as genes. Genes, through their
DNA “instructions,” create proteins that control specific functions or traits within the organism (hair color, blood type, and so on). Thus our entire genetic code
requires only four symbols! “Mapping the human genome”, that is, determining
the entire DNA sequence of humans, was a huge scientific undertaking, essentially completed in 2003, although the work of identifying specific genes and
their particular function is ongoing. It is known, for example, that the disease
cystic fibrosis is caused by a mutation in a particular gene (DNA sequence) that
is composed of about 230,000 nucleotides.
The most intuitive (although not the most efficient) string pattern-matching
algorithm compares the pattern (a string of length m) against the text (a string of
length n with n ≥ m), starting with the first character of the text and marching
through the pattern.