How different are string matching and integer matching in terms of time complexity?

I'm asking this especially in relation to Rabin Karp algorithm. Why is it faster to compute hash code for every substring and check for equality of hashcode with the hashcode of the given string than the naive method of just checking if amy of the substrings match with the given string?

  • 3
    $\begingroup$ What is integer matching? $\endgroup$ – Yuval Filmus Mar 10 '14 at 19:30
  • $\begingroup$ I don't know the exact terms to be used, by integer matching I meant checking equality of two integers. $\endgroup$ – Nitin Labhishetty Mar 11 '14 at 6:05

Checking whether two 32-bit integers are equal can be done in a single machine instruction.

Checking whether two strings are equal can take a lot longer. If my two strings are each 100 characters long, then checking whether those two strings are equal might require the equivalent of about 100 machine instructions: I have to check them, character by character.

In asymptotic complexity terms: checking equality of (fixed-precision) integers takes $O(1)$ time, checking equality of strings takes $O(n)$, where $n$ denotes the length of each string.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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