I am reading about the Rabin-Karp algorithm on Wikipedia and the time complexity mentioned in there is O(n+m). Now, from my understanding, m is necessarily between 0 and n, so in the best case the complexity is O(n) and in the worst case it is also O(2n)=O(n), so why isn't it just O(n)?
Basically, Robin-Karp expresses it's asymptotic notation as O(m+n) as a means to express the fact that it takes linear time relative to m+n and not just n. Essentially, the variables, m and n, have to mean something whenever you use asymptotic notation. For the case of the Robin-Karp algorithm, n represents the length of the text, and m represents the combined length of both the text and the pattern. Note that O(2n) means the same thing as O(n), because O(2n) is still a linear function of just n. However, in the case of Robin-Karp, m+n isn't really a function of just n. Rather, it's a function of both m and n, which are two independent variables. As such, O(m+n) doesn't mean the same thing as O(n) in the same way that O(2n) equates to O(n).
I hope that makes sense. :-P