Complexity of naive search

Let n be the text length and m be the pattern length. Naive search is $O(n m)$ in the worst case (e.g. aaaa... vs aaa...b).

Average case is often better, but without guarantee.

$$\textit{alignments} = n-m+1$$

Where used

Explains why log parsing and virus signature scans scale with naive search. The basis for KMP/Boyer-Moore and for inverted indexes.

Depth

Let n be the text length and m the pattern length. There are at most n minus m plus one relevant alignments. For each alignment, up to m character checks may be needed if the difference becomes visible late.

The actual work strongly depends on the data. Frequent early differences make the search practically inexpensive. Texts and patterns with long repeated prefixes, on the other hand, force almost complete checks at many positions. The analysis therefore multiplies the number of alignments by the maximum work per alignment.

Difficulty levels

1. Correctly determine the number of possible starting positions.
2. Distinguish between best and worst input patterns.
3. Count the number of character comparisons for concrete repetition patterns.

Pitfalls

The runtime should not be justified solely by the text length when the pattern length is variable. Conversely, a pessimistic bound is not a claim that every real input causes this amount of work.