> The time and space complexity are both O(n)<p>Actually the worst case time complexity is O(n * m). To see why, imagine searching for a big string of the form "aaa...aaax" in the much bigger string of the form "aaa...aaax".<p>The analysis case for average time is more tricky. You could intuitively think that it, too, should include an "m" term, right? But if strings are uniformly random then the probability of finding your way in to the n'th character of the needle from any given start position decreases geometrically (1, 1/256, 1/65536, ...). Since the sum of any such geometric series is a constant[0], we end up with O(n) * O(1) so it's just O(n).<p>[0]. <a href="https://en.wikipedia.org/wiki/Geometric_series#Sum" rel="nofollow">https://en.wikipedia.org/wiki/Geometric_series#Sum</a>