Data Structures & AlgorithmsNaive Pattern Matching

Naive Pattern Matching — The Fundamental Algorithm

LevelBeginner

Duration60 mins

TopicNaive Pattern Matching

3 / 4

Time Complexity O(n × m) — A Rigorous Analysis

Understanding the Quadratic Bound

The naive pattern matching algorithm has a time complexity of O(n × m) in the worst case, where n is the length of the text and m is the length of the pattern. This is often described as "quadratic" behavior, though technically it's quadratic only when m is proportional to n.

This complexity might seem acceptable for small inputs, but it becomes problematic at scale:

Text Size (n)	Pattern Size (m)	Worst-Case Operations
1,000	100	100,000
10,000	1,000	10,000,000
1,000,000	10,000	10,000,000,000
1,000,000	500,000	500,000,000,000,000

At 10 billion operations, even at 1 nanosecond per operation, we're looking at 10 seconds of computation. At 500 trillion, we're into years.

In this page, we'll rigorously analyze the time complexity, prove the worst-case bound, identify the input patterns that trigger it, and understand when the algorithm performs better.

What You Will Learn

By the end of this page, you will be able to prove the O(n × m) worst-case bound, construct pathological inputs that achieve this bound, analyze best-case and average-case behavior, and understand exactly why this complexity motivates the study of smarter algorithms.

Counting Operations

To analyze time complexity, we must first define what we're counting. For pattern matching, the dominant operation is the character comparison.

Why character comparison is the dominant operation:

It's performed in the innermost loop
It's where the algorithm spends the vast majority of its time
All other operations (loop increments, bounds checks) are constant-time overhead

The algorithm's structure:

for i = 0 to n-m:                    // Outer loop: n-m+1 iterations
    for j = 0 to m-1:                // Inner loop: up to m iterations
        if T[i+j] ≠ P[j]: break     // Character comparison + branch
        if j = m-1: record match    // Match found

Counting character comparisons:

Let C(i) be the number of character comparisons at position i. The total comparisons are:

$$\text{Total} = \sum_{i=0}^{n-m} C(i)$$

Each C(i) ranges from 1 (immediate failure) to m (complete comparison).

Why Count Comparisons?

In theoretical analysis, we focus on the dominant operation to simplify reasoning. In practice, cache effects, branch prediction, and memory access patterns also matter. But for asymptotic analysis, counting comparisons gives us the correct big-O bound.

Worst Case Analysis

Theorem: The naive pattern matching algorithm performs at most (n - m + 1) × m character comparisons.

Proof:

The outer loop runs exactly n - m + 1 times
The inner loop runs at most m times per outer iteration
Each inner iteration performs exactly 1 character comparison
Therefore, total comparisons ≤ (n - m + 1) × m

Simplifying the bound:

$(n - m + 1) \times m = nm - m^2 + m$

For asymptotic analysis:

If m ≤ n/2, this is O(nm)
If m = O(1) (constant pattern length), this is O(n)
If m = n/2, this is O(n²/4) = O(n²)
If m = n-1, this is O(n) (only 2 positions to check)

The "worst" worst case: When m ≈ √n, we get maximum (n - √n + 1) × √n ≈ n^{3/2} comparisons. But typically we express this as O(n × m) to capture the dependence on both parameters.

Constructing worst-case inputs:

The worst case occurs when:

Every position requires nearly all m comparisons before failing
Only the last characters differ

Pattern: P = "AAA...AAB" (m-1 A's followed by B) Text: T = "AAA...AAA" (all A's)

Example with m=4, n=8:

Pattern: "AAAB"
Text: "AAAAAAAA"

Position i	Comparisons	Result
0	A=A, A=A, A=A, A≠B → 4 comparisons	Fail at j=3
1	A=A, A=A, A=A, A≠B → 4 comparisons	Fail at j=3
2	A=A, A=A, A=A, A≠B → 4 comparisons	Fail at j=3
3	A=A, A=A, A=A, A≠B → 4 comparisons	Fail at j=3
4	A=A, A=A, A=A, A≠B → 4 comparisons	Fail at j=3

Total: 5 positions × 4 comparisons = 20 comparisons = (8-4+1) × 4 = 20 ✓

The bound is tight—we actually achieve it with this pathological input.

This Worst Case Is Realistic

Unlike some algorithms whose worst cases are purely theoretical, this worst case occurs in practice. Searching for a DNA sequence like 'AAAAAAAG' in a genome with long runs of A's triggers near-worst-case behavior. Similarly, searching for 'http://www.' in a file full of 'http://' strings.

Deriving the Bound Formally

Let's derive the complexity bound with full mathematical rigor.

Definitions:

$n$ = length of text $T$
$m$ = length of pattern $P$
$C_i$ = number of comparisons at position $i$ (where $0 \le i \le n-m$)
$C_{total}$ = total comparisons = $\sum_{i=0}^{n-m} C_i$

Bounds on $C_i$:

At each position, we perform at least 1 comparison (checking the first character) and at most $m$ comparisons (checking all characters):

$$1 \le C_i \le m \quad \text{for all } i$$

Lower bound on total comparisons:

$$C_{total} \ge \sum_{i=0}^{n-m} 1 = n - m + 1 = \Omega(n - m) = \Omega(n)$$

We must do at least one comparison per window, giving a linear lower bound.

Upper bound on total comparisons:

$$C_{total} \le \sum_{i=0}^{n-m} m = (n - m + 1) \times m = O(nm - m^2) = O(nm)$$

Conclusion: $C_{total} = O(nm)$, and this bound is tight (achievable).

worst_case_generator
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Generates worst-case inputs for the naive pattern matching algorithm.
 * Returns a text and pattern that achieves O(n × m) comparisons.
 */
function generateWorstCase(n: number, m: number): { text: string; pattern: string } {
    // Text: all A's
    const text = "A".repeat(n);
    
    // Pattern: (m-1) A's followed by B
    const pattern = "A".repeat(m - 1) + "B";
    
    return { text, pattern };
}
 
/**
 * Counts exact number of character comparisons in naive matching.
 */
function countComparisons(text: string, pattern: string): number {
    const n = text.length;
    const m = pattern.length;
    let comparisons = 0;
    
    for (let i = 0; i <= n - m; i++) {
        for (let j = 0; j < m; j++) {
            comparisons++; // Count this comparison
            if (text[i + j] !== pattern[j]) break;
        }
    }
    
    return comparisons;
}
 
// Verify the worst case
const { text, pattern } = generateWorstCase(1000, 100);
const actual = countComparisons(text, pattern);
const theoretical = (1000 - 100 + 1) * 100;
 
console.log(`Text length n = 1000, Pattern length m = 100`);
console.log(`Theoretical maximum: ${theoretical.toLocaleString()} comparisons`);
console.log(`Actual comparisons:  ${actual.toLocaleString()} comparisons`);
console.log(`Bound achieved: ${actual === theoretical ? "YES" : "NO"}`);
// Output: Bound achieved: YES

Best Case Analysis

Theorem: The naive pattern matching algorithm performs at least n - m + 1 character comparisons.

Proof:

The outer loop runs n - m + 1 times, and each iteration performs at least 1 comparison (to check the first character). Therefore:

$$C_{total} \ge n - m + 1 = \Omega(n)$$

Constructing best-case inputs:

The best case occurs when:

Every position fails immediately (at the first character)
The first character of the pattern never appears in the text (except where it should match)

Example:

Pattern: P = "XYZ"
Text: T = "AAAAAXYZAAAA" (one occurrence surrounded by A's)

At every position except the match, T[i] = 'A' ≠ 'X' = P[0], so we fail immediately with 1 comparison.

Position	Comparisons	Result
0	1	A≠X, fail
1	1	A≠X, fail
2	1	A≠X, fail
3	1	A≠X, fail
4	1	A≠X, fail
5	3	X=X, Y=Y, Z=Z, match!
6	1	A≠X, fail
7	1	A≠X, fail
8	1	A≠X, fail
9	1	A≠X, fail

Total: 9 × 1 + 1 × 3 = 12 comparisons (close to the minimum of n - m + 1 = 10).

True best case:

For the absolute minimum, assume no match exists and every position fails at the first character:

Pattern: "XYZ"
Text: "AAAAAAA" (all A's, length 7)

Positions 0-4: Each fails at first character with 1 comparison. Total: 5 comparisons = n - m + 1 = 7 - 3 + 1 = 5 ✓

Best case complexity: $\Omega(n - m) = \Omega(n)$ when pattern is constant length.

Best Case Is Common in Practice

When searching for a relatively rare pattern in typical text (like searching for 'xyzzy' in English prose), the first character will mismatch at most positions, giving near-linear performance. This is why naive matching often works acceptably in practice despite its poor worst case.

Average Case Analysis

Average case analysis is more complex because it depends on assumptions about the input distribution. Let's derive it under a common model.

Probabilistic model assumptions:

Both text and pattern contain characters from an alphabet of size $\sigma$
Each character is drawn uniformly at random from the alphabet
Text and pattern are independent random strings

Expected comparisons per position:

At any position $i$, what's the expected number of comparisons before a mismatch (or complete match)?

Let $C$ be the number of comparisons. We compare character by character until failure:

Probability of matching $k$ characters then failing: $(1/\sigma)^k \times (1 - 1/\sigma)$
Probability of matching all $m$ characters: $(1/\sigma)^m$

Expected comparisons at one position:

$$E[C] = \sum_{k=0}^{m-1} (k+1) \cdot (1/\sigma)^k \cdot (1 - 1/\sigma) + m \cdot (1/\sigma)^m$$

For large $\sigma$ (e.g., ASCII with 256 characters), this simplifies dramatically. The probability of even the first character matching is only $1/\sigma$, so:

$$E[C] \approx 1 + 1/\sigma + 1/\sigma^2 + ... = \frac{1}{1 - 1/\sigma} = \frac{\sigma}{\sigma - 1}$$

For $\sigma = 256$: $E[C] \approx 256/255 \approx 1.004$

For $\sigma = 26$ (letters only): $E[C] \approx 26/25 = 1.04$

For $\sigma = 4$ (DNA): $E[C] \approx 4/3 \approx 1.33$

For $\sigma = 2$ (binary): $E[C] \approx 2/1 = 2.00$

Expected Comparisons per Position by Alphabet Size
Alphabet	Size (σ)	Expected Comparisons	Overhead vs. Minimum
Binary	2	2.00	100% more
DNA (ACGT)	4	1.33	33% more
Lowercase letters	26	1.04	4% more
ASCII	256	1.004	0.4% more
Unicode BMP	65536	~1.00002	~0% more

Total expected comparisons:

$$E[C_{total}] = (n - m + 1) \times E[C] \approx (n - m + 1) \times \frac{\sigma}{\sigma - 1}$$

For large alphabets, this is essentially $O(n)$—linear time!

Key insight: The average case is much better than the worst case when the alphabet is reasonably large. The naive algorithm's poor worst case is triggered by highly repetitive patterns and texts, which are common in some domains (DNA, log files) but less common in natural language.

When average case fails:

Binary data: Only 2 symbols, so 50% chance of matching each character
DNA sequences: 4 nucleotides, strings are highly repetitive
Log files: Repeated timestamps, URLs, and patterns
Compressed data: Low entropy after compression

These domains require optimized algorithms.

Don't Rely on Average Case for Critical Systems

In security-sensitive contexts (e.g., input validation, intrusion detection), attackers can craft worst-case inputs. A system relying on average-case behavior can be denial-of-service attacked by malicious patterns. Always consider worst-case guarantees for adversarial settings.

Space Complexity

While time complexity is the primary concern, space complexity also matters.

Auxiliary space: O(1)

The naive algorithm uses only a constant amount of extra space:

Loop counters i and j: O(1)
Temporary storage for indices: O(1)

The algorithm doesn't create any data structures proportional to input size.

Total space: O(n + m)

If we count the input storage:

Text: O(n)
Pattern: O(m)
Auxiliary: O(1)
Total: O(n + m + 1) = O(n + m)

Output space: O(k) where k is the number of matches

If we store all match positions, the output can be O(n) in extreme cases (e.g., finding "A" in "AAAA" gives n matches).

Space-time tradeoff:

The naive algorithm sits at one extreme: minimal space, potentially expensive time. More sophisticated algorithms (like suffix arrays) trade space for speed:

Algorithm	Time	Auxiliary Space
Naive	O(nm)	O(1)
KMP	O(n+m)	O(m)
Rabin-Karp	O(n+m) avg	O(1)
Suffix Array	O(n+m) query	O(n) preprocessing

When O(1) Space Matters

In embedded systems, streaming contexts (processing data as it arrives), or when memory is severely constrained, the naive algorithm's O(1) auxiliary space is a genuine advantage. You can match patterns without allocating any additional memory proportional to input size.

Practical Performance Measurements

Asymptotic complexity tells part of the story, but practical performance depends on constants, cache behavior, and actual hardware. Let's examine empirical measurements.

performance_measurement
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * Measures the performance of naive pattern matching under different scenarios.
 */
function measurePerformance(
    text: string,
    pattern: string,
    label: string
): { comparisons: number; timeMs: number } {
    let comparisons = 0;
    const n = text.length;
    const m = pattern.length;
    
    const start = performance.now();
    
    for (let i = 0; i <= n - m; i++) {
        for (let j = 0; j < m; j++) {
            comparisons++;
            if (text[i + j] !== pattern[j]) break;
        }
    }
    
    const end = performance.now();
    
    console.log(`\n${label}:`);
    console.log(`  n = ${n.toLocaleString()}, m = ${m}`);
    console.log(`  Comparisons: ${comparisons.toLocaleString()}`);
    console.log(`  Time: ${(end - start).toFixed(2)}ms`);
    console.log(`  Throughput: ${((n / (end - start)) * 1000).toFixed(0)} chars/sec`);
    
    return { comparisons, timeMs: end - start };
}
 
// Test scenarios
const n = 100_000;
const m = 100;
 
// Worst case: near-match at every position
const worstText = "A".repeat(n);
const worstPattern = "A".repeat(m - 1) + "B";
measurePerformance(worstText, worstPattern, "WORST CASE (all near-matches)");
 
// Best case: immediate mismatch at every position
const bestText = "A".repeat(n);
const bestPattern = "B" + "A".repeat(m - 1);
measurePerformance(bestText, bestPattern, "BEST CASE (immediate mismatches)");
 
// Average case: random text and pattern
function randomString(length: number, alphabet: string): string {
    return Array.from({ length }, () => 
        alphabet[Math.floor(Math.random() * alphabet.length)]
    ).join("");
}
 
const avgText = randomString(n, "ABCDEFGHIJKLMNOPQRSTUVWXYZ");
const avgPattern = randomString(m, "ABCDEFGHIJKLMNOPQRSTUVWXYZ");
measurePerformance(avgText, avgPattern, "AVERAGE CASE (random 26-letter alphabet)");
 
// DNA case: 4-letter alphabet (more repetition)
const dnaText = randomString(n, "ACGT");
const dnaPattern = randomString(m, "ACGT");
measurePerformance(dnaText, dnaPattern, "DNA CASE (4-letter alphabet)");

Typical results (n=100,000, m=100):

Scenario	Comparisons	Time	Ratio to Best
Worst case	~10,000,000	~50ms	100x
Best case	~100,000	~0.5ms	1x
Average (26 letters)	~105,000	~0.6ms	~1x
DNA (4 letters)	~135,000	~0.8ms	~1.5x

The practical speedup from best to worst case is roughly mx (here, 100x). This matches theory: best case does 1 comparison per position, worst case does m.

Comparison with Linear-Time Algorithms

To put the naive algorithm's complexity in perspective, let's compare it with linear-time algorithms like KMP.

Theoretical comparison:

Algorithm	Preprocessing	Matching	Total	Space
Naive	O(1)	O(nm)	O(nm)	O(1)
KMP	O(m)	O(n)	O(n+m)	O(m)
Rabin-Karp	O(m)	O(n) avg	O(n+m) avg	O(1)
Z-Algorithm	O(n+m)	O(n+m)	O(n+m)	O(n+m)

When does the difference matter?

For small inputs or infrequent searches with typical text:

The naive algorithm is often acceptable
Its simplicity and O(1) space are advantages
Implementation overhead of KMP may outweigh theoretical gains

For large inputs, frequent searches, or adversarial conditions:

Linear-time algorithms are essential
The O(nm) vs O(n+m) difference becomes enormous
KMP's O(m) preprocessing is amortized over many searches

Approximate Comparison Counts: Naive vs KMP
n	m	Naive Worst	KMP	Speedup
1,000	100	~100,000	~1,100	~90x
10,000	500	~5,000,000	~10,500	~475x
100,000	1,000	~100,000,000	~101,000	~990x
1,000,000	10,000	~10^10	~1,010,000	~10,000x

The Crossover Point

In practice, there's a crossover point where the naive algorithm's simplicity wins below and KMP wins above. This depends on implementation quality, architecture, and access patterns. For typical modern systems, naive is competitive for m < 10-20 and random text, but KMP dominates for larger patterns or repetitive text.

Summary and Key Takeaways

We've conducted a thorough complexity analysis of the naive pattern matching algorithm. Let's consolidate the key insights:

Key Takeaways

•Worst case: O(n × m) comparisons — Achieved with repetitive text and near-matching patterns like 'AAA...AB' in 'AAA...A'.
•Best case: O(n) comparisons — Achieved when the first character mismatches at every position.
•Average case: O(n × σ/(σ-1)) ≈ O(n) — For large alphabets, near-linear in practice due to early termination.
•Space: O(1) auxiliary — No preprocessing, no extra data structures needed.
•The worst case is realistic — DNA sequences, log files, and binary data can trigger worst-case behavior.
•Large alphabets help — More distinct characters mean faster average-case performance.
•Comparison to KMP: up to O(m) speedup — Linear algorithms are dramatically faster for long patterns and repetitive text.

What's next:

Now that we understand the naive algorithm's limitations, the next page explores why improvement is needed. We'll examine real-world scenarios where O(n × m) is unacceptable and build motivation for the algorithms that will follow in subsequent modules.

Page Complete

You can now rigorously analyze the naive algorithm's complexity, construct worst-case inputs, and understand the conditions under which different performance characteristics emerge. This analysis forms the foundation for appreciating optimized algorithms.

3 / 4

Loading learning content...

Data Structures & AlgorithmsNaive Pattern Matching

Naive Pattern Matching — The Fundamental Algorithm

LevelBeginner

Duration60 mins

TopicNaive Pattern Matching

3 / 4

Time Complexity O(n × m) — A Rigorous Analysis

Understanding the Quadratic Bound

This complexity might seem acceptable for small inputs, but it becomes problematic at scale:

Text Size (n)	Pattern Size (m)	Worst-Case Operations
1,000	100	100,000
10,000	1,000	10,000,000
1,000,000	10,000	10,000,000,000
1,000,000	500,000	500,000,000,000,000

At 10 billion operations, even at 1 nanosecond per operation, we're looking at 10 seconds of computation. At 500 trillion, we're into years.

In this page, we'll rigorously analyze the time complexity, prove the worst-case bound, identify the input patterns that trigger it, and understand when the algorithm performs better.

What You Will Learn

Counting Operations

To analyze time complexity, we must first define what we're counting. For pattern matching, the dominant operation is the character comparison.

Why character comparison is the dominant operation:

It's performed in the innermost loop
It's where the algorithm spends the vast majority of its time
All other operations (loop increments, bounds checks) are constant-time overhead

The algorithm's structure:

for i = 0 to n-m:                    // Outer loop: n-m+1 iterations
    for j = 0 to m-1:                // Inner loop: up to m iterations
        if T[i+j] ≠ P[j]: break     // Character comparison + branch
        if j = m-1: record match    // Match found

Counting character comparisons:

Let C(i) be the number of character comparisons at position i. The total comparisons are:

$$\text{Total} = \sum_{i=0}^{n-m} C(i)$$

Each C(i) ranges from 1 (immediate failure) to m (complete comparison).

Why Count Comparisons?

Worst Case Analysis

Theorem: The naive pattern matching algorithm performs at most (n - m + 1) × m character comparisons.

Proof:

The outer loop runs exactly n - m + 1 times
The inner loop runs at most m times per outer iteration
Each inner iteration performs exactly 1 character comparison
Therefore, total comparisons ≤ (n - m + 1) × m

Simplifying the bound:

$(n - m + 1) \times m = nm - m^2 + m$

For asymptotic analysis:

If m ≤ n/2, this is O(nm)
If m = O(1) (constant pattern length), this is O(n)
If m = n/2, this is O(n²/4) = O(n²)
If m = n-1, this is O(n) (only 2 positions to check)

Constructing worst-case inputs:

The worst case occurs when:

Every position requires nearly all m comparisons before failing
Only the last characters differ

Pattern: P = "AAA...AAB" (m-1 A's followed by B) Text: T = "AAA...AAA" (all A's)

Example with m=4, n=8:

Pattern: "AAAB"
Text: "AAAAAAAA"

Position i	Comparisons	Result
0	A=A, A=A, A=A, A≠B → 4 comparisons	Fail at j=3
1	A=A, A=A, A=A, A≠B → 4 comparisons	Fail at j=3
2	A=A, A=A, A=A, A≠B → 4 comparisons	Fail at j=3
3	A=A, A=A, A=A, A≠B → 4 comparisons	Fail at j=3
4	A=A, A=A, A=A, A≠B → 4 comparisons	Fail at j=3

Total: 5 positions × 4 comparisons = 20 comparisons = (8-4+1) × 4 = 20 ✓

The bound is tight—we actually achieve it with this pathological input.

This Worst Case Is Realistic

Deriving the Bound Formally

Let's derive the complexity bound with full mathematical rigor.

Definitions:

$n$ = length of text $T$
$m$ = length of pattern $P$
$C_i$ = number of comparisons at position $i$ (where $0 \le i \le n-m$)
$C_{total}$ = total comparisons = $\sum_{i=0}^{n-m} C_i$

Bounds on $C_i$:

At each position, we perform at least 1 comparison (checking the first character) and at most $m$ comparisons (checking all characters):

$$1 \le C_i \le m \quad \text{for all } i$$

Lower bound on total comparisons:

$$C_{total} \ge \sum_{i=0}^{n-m} 1 = n - m + 1 = \Omega(n - m) = \Omega(n)$$

We must do at least one comparison per window, giving a linear lower bound.

Upper bound on total comparisons:

$$C_{total} \le \sum_{i=0}^{n-m} m = (n - m + 1) \times m = O(nm - m^2) = O(nm)$$

Conclusion: $C_{total} = O(nm)$, and this bound is tight (achievable).

worst_case_generator
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Generates worst-case inputs for the naive pattern matching algorithm.
 * Returns a text and pattern that achieves O(n × m) comparisons.
 */
function generateWorstCase(n: number, m: number): { text: string; pattern: string } {
    // Text: all A's
    const text = "A".repeat(n);
    
    // Pattern: (m-1) A's followed by B
    const pattern = "A".repeat(m - 1) + "B";
    
    return { text, pattern };
}
 
/**
 * Counts exact number of character comparisons in naive matching.
 */
function countComparisons(text: string, pattern: string): number {
    const n = text.length;
    const m = pattern.length;
    let comparisons = 0;
    
    for (let i = 0; i <= n - m; i++) {
        for (let j = 0; j < m; j++) {
            comparisons++; // Count this comparison
            if (text[i + j] !== pattern[j]) break;
        }
    }
    
    return comparisons;
}
 
// Verify the worst case
const { text, pattern } = generateWorstCase(1000, 100);
const actual = countComparisons(text, pattern);
const theoretical = (1000 - 100 + 1) * 100;
 
console.log(`Text length n = 1000, Pattern length m = 100`);
console.log(`Theoretical maximum: ${theoretical.toLocaleString()} comparisons`);
console.log(`Actual comparisons:  ${actual.toLocaleString()} comparisons`);
console.log(`Bound achieved: ${actual === theoretical ? "YES" : "NO"}`);
// Output: Bound achieved: YES

Best Case Analysis

Theorem: The naive pattern matching algorithm performs at least n - m + 1 character comparisons.

Proof:

The outer loop runs n - m + 1 times, and each iteration performs at least 1 comparison (to check the first character). Therefore:

$$C_{total} \ge n - m + 1 = \Omega(n)$$

Constructing best-case inputs:

The best case occurs when:

Every position fails immediately (at the first character)
The first character of the pattern never appears in the text (except where it should match)

Example:

Pattern: P = "XYZ"
Text: T = "AAAAAXYZAAAA" (one occurrence surrounded by A's)

At every position except the match, T[i] = 'A' ≠ 'X' = P[0], so we fail immediately with 1 comparison.

Position	Comparisons	Result
0	1	A≠X, fail
1	1	A≠X, fail
2	1	A≠X, fail
3	1	A≠X, fail
4	1	A≠X, fail
5	3	X=X, Y=Y, Z=Z, match!
6	1	A≠X, fail
7	1	A≠X, fail
8	1	A≠X, fail
9	1	A≠X, fail

Total: 9 × 1 + 1 × 3 = 12 comparisons (close to the minimum of n - m + 1 = 10).

True best case:

For the absolute minimum, assume no match exists and every position fails at the first character:

Pattern: "XYZ"
Text: "AAAAAAA" (all A's, length 7)

Positions 0-4: Each fails at first character with 1 comparison. Total: 5 comparisons = n - m + 1 = 7 - 3 + 1 = 5 ✓

Best case complexity: $\Omega(n - m) = \Omega(n)$ when pattern is constant length.

Best Case Is Common in Practice

Average Case Analysis

Average case analysis is more complex because it depends on assumptions about the input distribution. Let's derive it under a common model.

Probabilistic model assumptions:

Both text and pattern contain characters from an alphabet of size $\sigma$
Each character is drawn uniformly at random from the alphabet
Text and pattern are independent random strings

Expected comparisons per position:

At any position $i$, what's the expected number of comparisons before a mismatch (or complete match)?

Let $C$ be the number of comparisons. We compare character by character until failure:

Probability of matching $k$ characters then failing: $(1/\sigma)^k \times (1 - 1/\sigma)$
Probability of matching all $m$ characters: $(1/\sigma)^m$

Expected comparisons at one position:

$$E[C] = \sum_{k=0}^{m-1} (k+1) \cdot (1/\sigma)^k \cdot (1 - 1/\sigma) + m \cdot (1/\sigma)^m$$

For large $\sigma$ (e.g., ASCII with 256 characters), this simplifies dramatically. The probability of even the first character matching is only $1/\sigma$, so:

$$E[C] \approx 1 + 1/\sigma + 1/\sigma^2 + ... = \frac{1}{1 - 1/\sigma} = \frac{\sigma}{\sigma - 1}$$

For $\sigma = 256$: $E[C] \approx 256/255 \approx 1.004$

For $\sigma = 26$ (letters only): $E[C] \approx 26/25 = 1.04$

For $\sigma = 4$ (DNA): $E[C] \approx 4/3 \approx 1.33$

For $\sigma = 2$ (binary): $E[C] \approx 2/1 = 2.00$

Expected Comparisons per Position by Alphabet Size
Alphabet	Size (σ)	Expected Comparisons	Overhead vs. Minimum
Binary	2	2.00	100% more
DNA (ACGT)	4	1.33	33% more
Lowercase letters	26	1.04	4% more
ASCII	256	1.004	0.4% more
Unicode BMP	65536	~1.00002	~0% more

Total expected comparisons:

$$E[C_{total}] = (n - m + 1) \times E[C] \approx (n - m + 1) \times \frac{\sigma}{\sigma - 1}$$

For large alphabets, this is essentially $O(n)$—linear time!

When average case fails:

Binary data: Only 2 symbols, so 50% chance of matching each character
DNA sequences: 4 nucleotides, strings are highly repetitive
Log files: Repeated timestamps, URLs, and patterns
Compressed data: Low entropy after compression

These domains require optimized algorithms.

Don't Rely on Average Case for Critical Systems

Space Complexity

While time complexity is the primary concern, space complexity also matters.

Auxiliary space: O(1)

The naive algorithm uses only a constant amount of extra space:

Loop counters i and j: O(1)
Temporary storage for indices: O(1)

The algorithm doesn't create any data structures proportional to input size.

Total space: O(n + m)

If we count the input storage:

Text: O(n)
Pattern: O(m)
Auxiliary: O(1)
Total: O(n + m + 1) = O(n + m)

Output space: O(k) where k is the number of matches

If we store all match positions, the output can be O(n) in extreme cases (e.g., finding "A" in "AAAA" gives n matches).

Space-time tradeoff:

The naive algorithm sits at one extreme: minimal space, potentially expensive time. More sophisticated algorithms (like suffix arrays) trade space for speed:

Algorithm	Time	Auxiliary Space
Naive	O(nm)	O(1)
KMP	O(n+m)	O(m)
Rabin-Karp	O(n+m) avg	O(1)
Suffix Array	O(n+m) query	O(n) preprocessing

When O(1) Space Matters

Practical Performance Measurements

Asymptotic complexity tells part of the story, but practical performance depends on constants, cache behavior, and actual hardware. Let's examine empirical measurements.

performance_measurement
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * Measures the performance of naive pattern matching under different scenarios.
 */
function measurePerformance(
    text: string,
    pattern: string,
    label: string
): { comparisons: number; timeMs: number } {
    let comparisons = 0;
    const n = text.length;
    const m = pattern.length;
    
    const start = performance.now();
    
    for (let i = 0; i <= n - m; i++) {
        for (let j = 0; j < m; j++) {
            comparisons++;
            if (text[i + j] !== pattern[j]) break;
        }
    }
    
    const end = performance.now();
    
    console.log(`\n${label}:`);
    console.log(`  n = ${n.toLocaleString()}, m = ${m}`);
    console.log(`  Comparisons: ${comparisons.toLocaleString()}`);
    console.log(`  Time: ${(end - start).toFixed(2)}ms`);
    console.log(`  Throughput: ${((n / (end - start)) * 1000).toFixed(0)} chars/sec`);
    
    return { comparisons, timeMs: end - start };
}
 
// Test scenarios
const n = 100_000;
const m = 100;
 
// Worst case: near-match at every position
const worstText = "A".repeat(n);
const worstPattern = "A".repeat(m - 1) + "B";
measurePerformance(worstText, worstPattern, "WORST CASE (all near-matches)");
 
// Best case: immediate mismatch at every position
const bestText = "A".repeat(n);
const bestPattern = "B" + "A".repeat(m - 1);
measurePerformance(bestText, bestPattern, "BEST CASE (immediate mismatches)");
 
// Average case: random text and pattern
function randomString(length: number, alphabet: string): string {
    return Array.from({ length }, () => 
        alphabet[Math.floor(Math.random() * alphabet.length)]
    ).join("");
}
 
const avgText = randomString(n, "ABCDEFGHIJKLMNOPQRSTUVWXYZ");
const avgPattern = randomString(m, "ABCDEFGHIJKLMNOPQRSTUVWXYZ");
measurePerformance(avgText, avgPattern, "AVERAGE CASE (random 26-letter alphabet)");
 
// DNA case: 4-letter alphabet (more repetition)
const dnaText = randomString(n, "ACGT");
const dnaPattern = randomString(m, "ACGT");
measurePerformance(dnaText, dnaPattern, "DNA CASE (4-letter alphabet)");

Typical results (n=100,000, m=100):

Scenario	Comparisons	Time	Ratio to Best
Worst case	~10,000,000	~50ms	100x
Best case	~100,000	~0.5ms	1x
Average (26 letters)	~105,000	~0.6ms	~1x
DNA (4 letters)	~135,000	~0.8ms	~1.5x

The practical speedup from best to worst case is roughly mx (here, 100x). This matches theory: best case does 1 comparison per position, worst case does m.

Comparison with Linear-Time Algorithms

To put the naive algorithm's complexity in perspective, let's compare it with linear-time algorithms like KMP.

Theoretical comparison:

Algorithm	Preprocessing	Matching	Total	Space
Naive	O(1)	O(nm)	O(nm)	O(1)
KMP	O(m)	O(n)	O(n+m)	O(m)
Rabin-Karp	O(m)	O(n) avg	O(n+m) avg	O(1)
Z-Algorithm	O(n+m)	O(n+m)	O(n+m)	O(n+m)

When does the difference matter?

For small inputs or infrequent searches with typical text:

The naive algorithm is often acceptable
Its simplicity and O(1) space are advantages
Implementation overhead of KMP may outweigh theoretical gains

For large inputs, frequent searches, or adversarial conditions:

Linear-time algorithms are essential
The O(nm) vs O(n+m) difference becomes enormous
KMP's O(m) preprocessing is amortized over many searches

Approximate Comparison Counts: Naive vs KMP
n	m	Naive Worst	KMP	Speedup
1,000	100	~100,000	~1,100	~90x
10,000	500	~5,000,000	~10,500	~475x
100,000	1,000	~100,000,000	~101,000	~990x
1,000,000	10,000	~10^10	~1,010,000	~10,000x

The Crossover Point

Summary and Key Takeaways

We've conducted a thorough complexity analysis of the naive pattern matching algorithm. Let's consolidate the key insights:

Key Takeaways

•Worst case: O(n × m) comparisons — Achieved with repetitive text and near-matching patterns like 'AAA...AB' in 'AAA...A'.
•Best case: O(n) comparisons — Achieved when the first character mismatches at every position.
•Average case: O(n × σ/(σ-1)) ≈ O(n) — For large alphabets, near-linear in practice due to early termination.
•Space: O(1) auxiliary — No preprocessing, no extra data structures needed.
•The worst case is realistic — DNA sequences, log files, and binary data can trigger worst-case behavior.
•Large alphabets help — More distinct characters mean faster average-case performance.
•Comparison to KMP: up to O(m) speedup — Linear algorithms are dramatically faster for long patterns and repetitive text.

What's next:

Page Complete

3 / 4