liveBook · Manning

O(nxm)

As explained in Algorithms Every Programmer Should Know

A time bound proportional to the product of text length n and pattern length m.

O(nxm) describes work proportional to text length n multiplied by pattern length m. Character-by-character matching can reach this cost when it checks many pattern characters at each text position. section 4.0

String-matching algorithms can encounter this cost in different ways:

  • Brute-force matching may compare many characters before finding a mismatch. section 4.0
  • Rabin–Karp can degrade to O(nxm) when frequent hash collisions force character-by-character verification. section 4.4
  • Horspool can fall back to O(nxm) on tiny-alphabet or repetitive inputs when shifts stay short. section 6.4

A hash collision

A simple addition-based hash gives “ACT” and “CAT” the same value. Repeated collisions can force Rabin–Karp to verify characters and lose its average linear-time performance. section 4.4

Table 4.1 Comparison table of various string matching algorithms
Algorithm
Advantages
Disadvantages
Use cases
Rabin Karp
Converts strings to fast numeric hashes, allowing O(1) window sliding.
Degrades to catastrophic O(n x m) if weak hashes resulting in constant collisions
Plagiarism detection and bioinformatics
Knuth-Morris-Pratt
Guarantees deterministic O(n) time by creating Longest Prefix Suffix array
Wastes O(m) memory and provides zero speed advantage if the pattern lacks internal repetition.
Real time data streaming and log analysis
Boyer Moore
Achieves sub-linear performance by scanning right-to-left and skipping massive chunks of mismatched text.
Highly complex to implement the "Bad Character" tables, and degrades on highly repetitive text.
Text Editors and Integrated Development Environment (IDE)
Aho-Corasick
Constructs a state-machine to search for thousands of different patterns simultaneously in a single O(n) pass
Imposes massive memory overhead to build and store the deterministic finite states
Mass virus scanning against massive signature databases

Compare how Rabin–Karp, KMP, Boyer–Moore, and Aho–Corasick trade performance against other costs and limitations. section 4.0

How Algorithms Every Programmer Should Know covers it

How deep it goes
Explains character comparisons and collision-driven degradation, but does not derive a formal bound.
Examples
Uses ACT and CAT to illustrate a hash collision, and binary or DNA inputs to illustrate Horspool’s slowdown.
What you can do after
Diagnose worst-case slowdowns by identifying frequent hash collisions or input alphabets that force short shifts.
How it connects
Connects string matching with Rabin–Karp hash collisions and Horspool’s tiny-alphabet worst case.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.