$n$ : length of text T

$m$ : length of pattern P

When I study Rabin-Karp algorithm, I learned the best case of this algorithm is $\theta(n-m+1)$. Because if a hashed number is too small to modulo by some other number.

But when I'm talking with my friends about this best complexity, I was very curios that does above theta notation can be represented by $\theta(n)$ if $n$ is asymptotic to infinity?

First time, it was reasonable to me that $\theta(n)=\theta(n-m+1)$ is correct because it is asymptotic notation. But if $m$ is always $n-1$, can we use $\theta(n)$ in this situation? I'm confusing about notation concept and what I'm curious is below question.

What is the right time complexity notation of Rabin-Karp algorithm?

$\theta(n)$ or $\theta(n-m+1)$?


2 Answers 2


The running time you quote isn't correct. If $n = m$ then it takes $\Omega(n)$ to verify that $T = P$. The best case running time of any string matching algorithm is $\Omega(m)$, since this is how long it takes to verify a match. Perhaps you are disregarding the time it takes to compute the hashes.

Ignoring all of this, let us suppose that we are considering an algorithm whose running time is $\Theta(n-m+1)$, where $m \leq n$ are two parameters. As your example makes clear, this is not the same as $\Theta(n)$, since if $m$ is close to $n$ then $n-m+1$ is much smaller than $n$. Generally speaking, an asymptotic expression depending on two parameters cannot be reduced to an asymptotic expression depending on only one of them.

In practice, often $m$ is itself a known function of $n$, and this can be used to reduce $\Theta(n-m+1)$ to an asymptotic expression depending on a single parameter. For example, if $m = n/2$ then $\Theta(n-m+1) = \Theta(n)$, whereas if $m = n$, then $\Theta(n-m+1) = \Theta(1)$.


Rabin-Karp algo consists of two steps:

  • hash first m symbols of input and the pattern, which takes $\theta(m)$
  • check first n-m+1 positions of the file comparing hashes of next m chars at each position to the pattern hash, which takes $\theta(n-m+1)$

Most probably, your source mentioned only the second step complexity.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.