206
Recursion, Recurrence Relations, and Analysis of Algorithms
T 1 T 2 T 3 … T m T m+1 … T n
`
`
`
`
P 1 P 2 P 3 … P m
If all m characters match, the pattern has been found. If there is a mismatch at some
point between the text and the pattern, the pattern slides over one character in the
text, and the matching process begins again.
T 1 T 2 T 3 … T m T m+1 … T n
` `
`
P 1 P 2 P 3 … P m
The last segment of text where the pattern could possibly occur is the last m
elements of the text. This segment begins at T n−m+1 , as shown below.
T 1 T 2 T 3 … T n−m+1 T n−m+2 … T n−m+m = T n
`
`
`
P 1 P 2 … P m
For example, if the text is 23 characters long and the pattern is 5 characters long,
then the last piece of text that can possibly hold the pattern is T 19 T 20 T 21 T 22 T 23 .
The unit of work in this algorithm is comparisons between a text character and
a pattern character. The best case occurs when the pattern is found as the first m
characters of the text, which requires m comparisons. The worst case is when the
pattern does not occur in the text at all, and the pattern “window” slides all the way
over to T n−m+1 . From each of those n − m + 1 starting points, the pattern fails
to be found, but the worst case is if the pattern almost matches and only the last
character fails. For example, consider the text and pattern shown:
Text: TTTTTTTTTTTTT
Pattern: TTTTTS
This example requires m comparisons (the first m − 1 are matches and only the
mth comparison fails) at each of the n − m + 1 starting positions, making the total
number of comparisons m(n − m + 1).
Analysis Using Recurrence Relations
In this section we will analyze algorithms that are defined recursively. Because
much of the activity of a recursive algorithm takes place “out of sight” in the
many invocations that can occur, an analysis using the direct counting technique
of Example 27 won’t work. Analysis of recursive algorithms usually involves
solving a recurrence relation.
Recursion, Recurrence Relations, and Analysis of Algorithms
T 1 T 2 T 3 … T m T m+1 … T n
`
`
`
`
P 1 P 2 P 3 … P m
If all m characters match, the pattern has been found. If there is a mismatch at some
point between the text and the pattern, the pattern slides over one character in the
text, and the matching process begins again.
T 1 T 2 T 3 … T m T m+1 … T n
` `
`
P 1 P 2 P 3 … P m
The last segment of text where the pattern could possibly occur is the last m
elements of the text. This segment begins at T n−m+1 , as shown below.
T 1 T 2 T 3 … T n−m+1 T n−m+2 … T n−m+m = T n
`
`
`
P 1 P 2 … P m
For example, if the text is 23 characters long and the pattern is 5 characters long,
then the last piece of text that can possibly hold the pattern is T 19 T 20 T 21 T 22 T 23 .
The unit of work in this algorithm is comparisons between a text character and
a pattern character. The best case occurs when the pattern is found as the first m
characters of the text, which requires m comparisons. The worst case is when the
pattern does not occur in the text at all, and the pattern “window” slides all the way
over to T n−m+1 . From each of those n − m + 1 starting points, the pattern fails
to be found, but the worst case is if the pattern almost matches and only the last
character fails. For example, consider the text and pattern shown:
Text: TTTTTTTTTTTTT
Pattern: TTTTTS
This example requires m comparisons (the first m − 1 are matches and only the
mth comparison fails) at each of the n − m + 1 starting positions, making the total
number of comparisons m(n − m + 1).
Analysis Using Recurrence Relations
In this section we will analyze algorithms that are defined recursively. Because
much of the activity of a recursive algorithm takes place “out of sight” in the
many invocations that can occur, an analysis using the direct counting technique
of Example 27 won’t work. Analysis of recursive algorithms usually involves
solving a recurrence relation.