Time Complexity: O(n + m) Average, O(n × m) Worst

The Rabin-Karp algorithm has a fascinating complexity profile: it achieves O(n + m) expected time in typical cases, but can degrade to O(n × m) worst case under specific conditions. This dual nature distinguishes it from algorithms like KMP that guarantee O(n + m) always.

Understanding when and why Rabin-Karp performs well—and when it might struggle—is crucial for making informed algorithm choices. This page provides a rigorous complexity analysis that equips you to predict Rabin-Karp's behavior in any scenario.

Before pattern matching begins, Rabin-Karp performs several preprocessing steps. Let's analyze each one.

Step 1: Compute pattern hash

for each character c in pattern:  // m iterations
    hash = (hash * base + ord(c)) % mod  // O(1) each

Total: O(m) time

Step 2: Compute base^(m-1) mod q

// Method 1: Iterative (naïve)
power = 1
for i = 0 to m-2:  // m-1 iterations
    power = (power * base) % mod  // O(1) each
    
// Method 2: Fast exponentiation
power = modpow(base, m-1, mod)  // O(log m)

Iterative: O(m) time Fast exponentiation: O(log m) time

Step 3: Compute first window hash

for i = 0 to m-1:  // m iterations
    window_hash = (window_hash * base + ord(text[i])) % mod  // O(1)

Total: O(m) time

Total preprocessing: O(m)

The preprocessing time is linear in pattern length, independent of text length. This is important: we do O(m) work once, then O(1) work per position during matching.

Space complexity of preprocessing:

• Pattern hash: O(1)
• Base power: O(1)
• Window hash: O(1)
• Total auxiliary space: O(1)

Rabin-Karp has excellent space efficiency—it uses only constant extra memory beyond the input strings.

The matching phase is where Rabin-Karp's complexity depends on the input. Let's analyze it carefully.

Main loop structure:

for i = 0 to n - m:  // (n - m + 1) iterations
    if window_hash == pattern_hash:  // O(1) comparison
        if verify(text, pattern, i):  // O(m) when called
            report match
    roll_hash()  // O(1)

Per-iteration breakdown:

• Hash comparison: O(1)
• Hash rolling: O(1)
• Verification (conditional): O(m)

Key question: How often is verification performed?

Verification is called whenever window_hash == pattern_hash. This happens when:

1. There's an actual match (we want this)
2. There's a hash collision (spurious hit)

Let k = number of actual matches + number of spurious hits

Matching phase time complexity:

Total time = Loop iterations × O(1) + Verifications × O(m)
           = (n - m + 1) × O(1) + k × O(m)
           = O(n) + O(km)
           = O(n + km)

Where k = (actual matches) + (spurious hits)

The critical insight:

The complexity depends entirely on k:

• If k is small (constant or logarithmic): O(n + m) = O(n)
• If k is large (proportional to n): O(nm)

For typical inputs with few matches and rare collisions, k is very small. For pathological inputs, k can be large.

Let's derive the expected running time rigorously, assuming our hash function distributes values uniformly.

Probability model:

• Modulus: q (a large prime)
• Position count: N = n - m + 1
• At each position, hash equals pattern hash with probability:
  • 1 if strings match (actual match)
  • 1/q if strings differ (spurious hit via collision)

Expected number of spurious hits:

For positions where text doesn't match pattern (at most N positions):

E[spurious hits] = N × P(collision)
                 = N × (1/q)
                 = (n - m + 1) / q

With q = 10^9 and n = 10^6:

E[spurious hits] = 10^6 / 10^9 = 0.001

We expect essentially zero spurious hits for typical inputs!

Expected verification count:

Let A = number of actual matches (depends on pattern and text).

E[verifications] = A + E[spurious hits]
                 = A + (n - m + 1) / q
                 ≈ A  (when q is large)

Expected total time:

E[total time] = Preprocessing + Matching
             = O(m) + O(n) + E[verifications] × O(m)
             = O(m) + O(n) + O(Am) + O((n-m+1)/q × m)
             = O(m + n + Am + nm/q)

When q ≫ nm (which is typical):

E[total time] = O(n + m + Am)

If A is O(1) (few matches), this is O(n + m).

Understanding the worst case helps identify when Rabin-Karp might underperform and when alternatives should be considered.

Worst case scenario:

The algorithm achieves O(nm) when verification is required at every position. This happens when:

1. Pattern matches at every position, OR
2. Every position is a spurious hit

Example 1: Pattern matches everywhere

Text:    AAAAAAAAA (n = 9)
Pattern: AA        (m = 2)
Matches at: 0, 1, 2, 3, 4, 5, 6, 7 (8 matches!)

Work = 8 positions × O(2) verification each = O(16) = O(nm)

This is unavoidable—if the pattern truly appears everywhere, we must verify everywhere.

Example 2: Adversarial hash collisions

An attacker who knows the hash parameters can construct input where every substring hashes to the pattern's hash value, forcing O(m) verification at each of n-m+1 positions.

Probability of worst case via collisions:

For the worst case to occur through collisions alone (not actual matches), every single position must have a spurious hit:

P(all positions collide) = (1/q)^N
                         = (1/10^9)^(n-m+1)
                         ≈ 0  (exponentially small)

This is essentially impossible with random input. Worst case through collisions requires adversarial construction.

Practical implications:

1. For random/typical text: O(n + m) expected, worst case extremely unlikely
2. For user-provided input in security context: Consider worst case possible
3. For highly repetitive text with short patterns: Expect near-worst-case

Rabin-Karp has excellent space efficiency. Let's analyze it carefully.

Variables used:

1. Pattern hash — Single integer: O(1)
2. Window hash — Single integer: O(1)
3. Base power (b^{m-1}) — Single integer: O(1)
4. Position counters — Constants: O(1)
5. Hash parameters (base, mod) — Constants: O(1)

Total auxiliary space: O(1)

Rabin-Karp uses constant extra memory regardless of input size. This is optimal for a pattern matching algorithm.

Memory access patterns:

Rabin-Karp has favorable memory access patterns:

1. Sequential text access — We read text characters in order, maximizing cache efficiency
2. Pattern accessed only during verification — And then sequentially
3. No auxiliary data structures — No arrays to allocate or traverse

For very large texts that don't fit in memory, Rabin-Karp can be implemented as a streaming algorithm, processing the text one character at a time without buffering.

Streaming implementation:

while has_more_input():
    char = read_next_char()
    update_hash(char, outgoing_char)
    if hash_matches():
        verify_or_report_possible_match()
    outgoing_char = char_at(current_pos - m + 1)

This enables pattern matching on texts larger than available memory.

Let's compare Rabin-Karp's complexity with other major string matching algorithms to understand when each is preferable.

Key observations:

1. Rabin-Karp vs Naive: Same worst case, but vastly better expected case. The hash filter eliminates most comparisons.

2. Rabin-Karp vs KMP: KMP guarantees O(n+m) always. Rabin-Karp only achieves this in expectation. However:

   • Rabin-Karp is simpler to implement
   • Rabin-Karp handles multiple patterns elegantly
   • KMP is preferred when worst-case guarantees matter

3. Rabin-Karp vs Boyer-Moore: Boyer-Moore can be sublinear O(n/m) when pattern is long and mismatches occur early. Rabin-Karp is always at least O(n). Boyer-Moore is preferred for single long patterns.

4. Multiple patterns: Rabin-Karp shines when searching for k patterns simultaneously—preprocessing is O(km) but matching remains O(n + km) expected.

Asymptotic complexity tells part of the story, but practical performance depends on additional factors. Let's examine them.

Factor 1: Constant factors in hash computation

Each hash update involves:

• 1 multiplication
• 1 subtraction
• 1 multiplication
• 1 addition
• 1 modulo operation

The modulo operation (%) is often the slowest—it involves integer division. Using a power-of-two modulus enables bit masking instead:

hash % (2^k) = hash & ((1 << k) - 1)  // Much faster!

However, power-of-two moduli have worse collision properties than primes.

Factor 2: Branch prediction

The main loop has a conditional check:

if window_hash == pattern_hash:  // Usually false
    verify()

Since matches are rare, the branch predictor learns to assume 'not equal' and proceeds efficiently. Spurious hits cause branch mispredictions, adding ~10-20 cycles each.

Factor 3: Cache behavior

Rabin-Karp reads text sequentially, which is cache-friendly:

• Each character is read once for hash update
• Second read only for verification (rare)
• Pattern fits in L1 cache for typical sizes

Factor 4: Integer overflow handling

In languages without arbitrary-precision integers (C++, Java):

• Must use 64-bit integers for intermediate values
• Consider using Barrett reduction for fast modulo
• Or use 128-bit integers for very large moduli