Tight bounds on the complexity of the Boyer-Moore string matching algorithm

The problem of finding all occurrences of a pattern of length m in a text of length n is considered. It is shown that the Boyer-Moore string matching algorithm performs roughly 3n comparisons and that this bound is tight up to O(n/m); more precisely, an upper bound of 3n-3(n-m+1)/(m+2) comparisons is shown, as is a lower bound of 3n(1-o(1)) comparisons, as n/m→∞ and m→∞. While the upper bound is somewhat involved, its main elements provide a simple proof of a 4n upper bound for the same algorithm.