Why is naive substring search O(n*m) in the worst case yet near O(n) on ordinary text?
answer
- count the offsets, then the work at each
- what happens after a mismatch at an offset
- the worst case needs near-misses everywhere
- one repeated symbol, pattern differing on its last
- (n-m+1) offsets times m comparisons each
basics
~20 sNaive search retries the pattern at every offset, so each of the roughly n offsets can cost up to m comparisons. On ordinary text most offsets mismatch within a symbol or two, so the scan behaves near-linearly.
solid answer
~40 sNaive matching tries every starting offset `s` from 0 to n-m and compares the pattern forward until a mismatch or a full match. That is (n-m+1) offsets times up to m comparisons, so O(n*m) in the worst case. Reaching that bound needs near-misses everywhere: a text of one endlessly repeated symbol against a pattern that repeats the same symbol m-1 times and then differs, so every alignment matches m-1 symbols before failing on the last. Ordinary text does not look like that — over a large alphabet the first or second comparison usually fails, so the expected work per offset is a small constant and the scan is effectively O(n). The O(n*m) label is an upper bound, not a forecast, and naive search keeps two real advantages: no preprocessing and O(1) extra space.
code
pseudocode · 9 linesn = length(text)
m = length(pat)
for s in 0..n-m:
j = 0
while j < m and text[s + j] == pat[j]:
j = j + 1
if j == m:
report match at s
// nothing learned at s is carried to s + 1go deeper
Be ready to state the two loops and multiply them out: about n starting offsets, up to m comparisons at each. Say why the count is (n-m+1)m rather than exactly nm.
Explain why the bound is rarely reached. Over a large alphabet the first or second comparison usually fails, so expected work per offset is a small constant and the scan is effectively linear.
Show judgment about when naive is the correct production answer — short pattern, modest text, one-shot scan, no preprocessing budget — and name the repetitive inputs that turn it into a latency risk worth measuring.
Own the framing that an O(n*m) label is an upper bound, not a forecast. Insist teams measure comparison counts on their real corpus before trading simple, allocation-free code for a preprocessing matcher.
## The algorithm Naive (brute-force) substring search asks a simple question at every position: does the pattern start here? For a text of length n and a pattern of length m, it walks the starting offsets `s = 0, 1, ..., n-m` and, at each one, compares `text[s+j]` with `pat[j]` for j = 0, 1, 2, ... It stops that inner walk at the first mismatch and moves to offset `s+1`, or reports a match when j reaches m. The defining property is that it **carries nothing across offsets**. Whatever it learned while failing at offset `s` — say it matched 30 symbols before the 31st disagreed — is thrown away, and offset `s+1` starts from j = 0. That is the whole reason smarter matchers exist: they preserve information about the prefix already matched, or they test many offsets with one cheap fingerprint instead of a full comparison. ## Counting the work There are (n-m+1) offsets. Each offset performs at least one comparison and at most m. So the total comparison count is between (n-m+1) and (n-m+1)*m, which is why the worst case is written O(n*m) — usually with the harmless simplification that m is much smaller than n. Space is O(1) beyond the two indices: there is no table, no allocation, no build phase. ## Constructing the worst case To actually reach (n-m+1)*m you need every offset to be a **near miss** — matching almost the whole pattern before failing. Take a long read consisting of a single repeated symbol, the shape you see in low-complexity biological sequence data: `AAAAAAAA...A`. Search it for `AAA...AB` (m-1 copies of the repeated symbol followed by a different one). Every alignment marches through m-1 equal symbols, hits the final disagreement, and restarts one position later having gained nothing. Concretely, with a text of six `A` and the pattern `AAB`, there are 4 offsets and each does 3 comparisons: 12 comparisons for a text of 6. The mirror image is just as bad and is often forgotten: a text of one repeated symbol searched for a pattern of that same repeated symbol. Now every offset is a **full** match, so every offset spends m comparisons and reports an occurrence. Here part of the cost is genuine output — there really are n-m+1 occurrences — but naive search still pays m comparisons for each of them, where a matcher that carries information across offsets can report all of them in linear total time. ## Why real text is fast Natural language, source code, log lines and most binary payloads draw from an alphabet of dozens to hundreds of distinct symbols, and consecutive symbols are far from uniform but nowhere near constant. The probability that a random offset agrees with the pattern's first symbol is small; the probability it agrees on the first two is smaller still. So the inner loop almost always terminates after one or two comparisons, the expected comparisons per offset is a small constant c, and the total is about c*n. This is why naive search is the right default for a one-shot scan of a modest text with a short pattern — and why libraries and editors got away with it for decades before anyone reached for a skipping algorithm. ## The direction of the claim Big-O is an **upper** bound. Saying naive search is O(n*m) does not assert that it ever exhibits n*m work on your data; it asserts that nothing worse can happen. Conversely, "it's fast in practice" is not a bound: the moment your input becomes repetitive — a padded fixed-width record, a run-length-ish data stream, a file of one repeated separator, a corpus of near-duplicate templates — the near-miss structure appears and the quadratic behaviour is real. That is the honest answer in an interview: state the bound, state the input shape that reaches it, and state what your actual data looks like. ## What it costs you to improve Every alternative buys speed with something. A fingerprint-based scan (rolling hash) makes each offset O(1) expected but needs a verification step and gives only an expected bound. An automaton or prefix-reuse matcher gives a worst-case linear guarantee but needs a preprocessing pass over the pattern and a table to hold. If the scan happens once, on a short pattern, in a place where simplicity matters, the preprocessing may cost more than it saves. Measure comparisons on the real corpus before trading the two-loop version away.
- Does the worst case require the pattern to be absent from the text?No. Both extremes reach it. A text of one repeated symbol searched for that symbol repeated m-1 times plus a different one gives a near miss at every offset and zero matches. The same text searched for the symbol repeated m times gives a full match at every offset — n-m+1 occurrences, each costing m comparisons. Near-misses and total matches are equally expensive for naive search.
- What is naive matching's extra space cost, and why does that matter?O(1) beyond the two loop indices — no preprocessing table, no allocation, one forward pass over the text with good locality. That is a real advantage for short patterns and one-shot scans: an algorithm with a worst-case linear guarantee has to build and hold a structure first, and for a pattern of a dozen symbols that build can cost more than the scan it saves.
- Where does naive matching's wasted work actually go?Into re-comparing symbols it has already read. After failing at offset s having matched j symbols, it knows those j symbols of the text exactly, then discards that knowledge and re-reads j-1 of them at offset s+1. Every faster exact matcher is, in some form, a scheme for not throwing that information away.
saying these in an interview costs you the question
- Says naive search is always O(n*m) on any input
- Thinks a mismatch lets naive search skip m positions
- Claims naive search needs a preprocessing pass first
- Treats the upper bound as the cost actually observed
- Ignores that a large alphabet is why real text scans fast