Time Complexity: O(n + m)

The KMP algorithm's claim to fame is its O(n + m) time complexity—linear in both the text length n and the pattern length m. This guarantee is profound because it means:

1. No input can cause slowdown: Unlike naive O(n×m) matching, adversarial inputs can't trigger pathological behavior.
2. Predictable performance: Processing time scales linearly with input size, essential for real-time systems.
3. Separable phases: O(m) preprocessing + O(n) matching means preprocessing is "free" when searching multiple texts.

But why is KMP O(n + m)? The answer isn't immediately obvious—the algorithm has loops within loops, fallback cascades, and pointer movements that seem potentially expensive. Let's prove this bound rigorously.

The KMP algorithm has two distinct phases:

Phase 1: Preprocessing (Build LPS Array)

• Input: Pattern of length m
• Output: LPS array of length m
• Goal: Compute LPS[i] for all 0 ≤ i < m

Phase 2: Matching (Search for Pattern in Text)

• Input: Text of length n, Pattern of length m, LPS array
• Output: All starting positions of pattern in text
• Goal: Find all occurrences

We'll prove each phase has linear complexity separately.

The LPS array construction has a loop with two possible branches:

1. Match: pattern[i] == pattern[length] → increment both, move forward
2. Mismatch with length > 0: fallback length = lps[length-1]
3. Mismatch with length = 0: just move i forward

The concern is branch 2—the fallback. Could we spiral into many fallbacks per index i?

The Amortized Argument:

Define a potential function Φ = length (the current value of the length variable).

• Initially: Φ = 0
• Finally: Φ ≥ 0 (length is never negative)

Analyzing each operation:

1. Match (increment length): Φ increases by 1. This happens at most m-1 times (can't exceed m-1 matches as i goes from 1 to m-1).

2. Fallback (length = lps[length-1]): Φ decreases. Since lps[length-1] < length always, each fallback reduces Φ by at least 1.

3. Mismatch with length=0: Φ stays at 0, i advances.

Detailed Proof:

Let's count operations precisely:

• i++ happens exactly m-1 times (i goes from 1 to m-1)
• Each i++ is accompanied by either:
  • A match (length++), OR
  • A final mismatch after 0+ fallbacks when length=0
• Each fallback decreases length by at least 1
• Total fallbacks ≤ total length increases (since length ≥ 0)
• Total length increases ≤ m-1 (bounded by i advances)
• Therefore: total fallbacks ≤ m-1

Total operations:

• Comparisons: at most m-1 (one significant comparison per i advance)
• Fallbacks: at most m-1
• i advances: exactly m-1

Total: O(m)

The matching phase uses the same analysis approach. Define:

• i = text pointer (starts at 0, ends at n)
• j = pattern pointer (oscillates between 0 and m)
• Potential Φ = j

Operations in the matching loop:

1. Match (i++, j++): Both pointers advance. Φ increases by 1.

2. Full match (j == m): j = lps[m-1]. Φ might decrease significantly, but this is fine—we earned those increases.

3. Mismatch with j > 0: j = lps[j-1]. Φ decreases.

4. Mismatch with j = 0: i++. Φ stays at 0.

The Bound:

• The text pointer i advances exactly n times total (from 0 to n)
• Each i advance is accompanied by a match (j++) OR is a "restart" when j=0
• Total j increases ≤ n (one per text character, at most)
• Total j decreases ≤ total j increases (since j ≥ 0)
• Therefore total fallback operations ≤ n

Total operations in matching phase:

• Text comparisons: ≤ 2n (each i advance might be paired with one fallback cascade, but total fallbacks ≤ n)
• Pointer operations: O(n)

Total: O(n)

Putting both phases together:

Total Time Complexity:

• Preprocessing: O(m)
• Matching: O(n)
• Combined: O(n + m)

This is optimal for any algorithm that must:

1. Read the entire pattern (Ω(m) lower bound)
2. Potentially read the entire text (Ω(n) lower bound)

Space Complexity:

• LPS array: O(m)
• Pattern storage: O(m) (if not passed by reference)
• Text storage: O(n) (if not streaming)
• Other variables: O(1)

Total space: O(m) beyond input storage, since the LPS array is the only additional data structure.

Let's quantify the improvement KMP provides over the naive algorithm:

Naive Algorithm:

• Time: O(n × m) worst case, O(n) best case
• Space: O(1)
• Worst case trigger: Repetitive patterns in repetitive text

KMP Algorithm:

• Time: O(n + m) always
• Space: O(m) for LPS array
• No worst case trigger exists

Real-World Impact:

For a genome sequence search (n = 3 billion, m = 1,000):

• Naive worst case: ~3 quadrillion comparisons (3 × 10¹⁵)
• KMP: ~3 billion comparisons (3 × 10⁹)
• Difference: 1 million× faster

At 10 billion comparisons per second:

• Naive: ~3.5 days (worst case)
• KMP: ~0.3 seconds

Let's visualize why the text pointer never backtracks and why total operations are bounded.

Key Visualization: The Text Pointer Only Advances

Why This Proves O(n):

1. The text pointer i advances to n, taking n steps
2. Each step either:
   • Increments j (bounded by total j increments)
   • Or occurs when j = 0
3. Total j increments ≤ n (one per text position at most)
4. Total j decrements ≤ n (bounded by increments)
5. Therefore total work ≤ 2n = O(n)

Is O(n + m) the best possible? For any algorithm that solves the pattern matching problem, can we prove a lower bound?

Theorem: Any algorithm that finds all occurrences of a pattern in a text requires Ω(n + m) comparisons in the worst case.

Proof Sketch:

1. Reading the pattern: To know what to search for, we must examine each of the m pattern characters at least once. Lower bound: Ω(m).

2. Reading the text: Consider the text where every position could potentially be a match start (e.g., text = pattern repeated with modifications). We must examine each of the n text characters. Lower bound: Ω(n).

3. Combined lower bound: Ω(n + m)

Conclusion: KMP is asymptotically optimal. No comparison-based algorithm can beat O(n + m).