Boyer-Moore string search algorithm run time complexity

algorithmboyer-moorepattern matchingstring

In Boyer-Moore string search algorithm wiki link, it is stated that worst case complexity of Boyer-Moore is

  1. O(m+n) if pattern does not appear in the text
  2. O(mn) if pattern does appear in the text

But in String Search Algorithm wiki, it is stated that worst case complexity of Boyer-Moore is O(n). Why is this disparity ?

Here also it is stated to be O(mn) in worst case.

So what is the correct run time complexity of Boyer-Moore algorithm ?

Best Answer

The difference comes from different definitions. In the general string search page, algorithms complexity is split to preprocessing and matching, whereas the page for the algorithm itself didn't make that distinction.

The preprocessing will be Θ(m + k) plus O(n) for matching.