title: Boyer-Moore string search algorithm run time complexity
body: <p>In <a href="https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm" rel="nofollow">Boyer-Moore string search algorithm wiki </a> link, it is stated that worst case complexity of Boyer-Moore is</p>
  
  <ol>
  <li><strong><em>O(m+n)</em></strong> if pattern does not appear in the text</li>
  <li><strong><em>O(mn)</em></strong> if pattern does appear in the text</li>
  </ol>
  
  <p>But in <a href="https://en.wikipedia.org/wiki/String_searching_algorithm" rel="nofollow">String Search Algorithm wiki</a>, it is stated that worst case complexity of Boyer-Moore is <strong><em>O(n)</em></strong>. Why is this disparity ?</p>
  
  <p><a href="http://www-igm.univ-mlv.fr/~lecroq/string/node14.html" rel="nofollow">Here</a> also it is stated to be O(mn) in worst case.</p>
  
  <p>So what is the correct run time complexity of Boyer-Moore algorithm ?</p>