You are viewing a single comment's thread. Return to all comments →
None of these solutions are O(n), actually. You have to take into consideration the time it takes to read a string, O(c), where c is the number of characters in the string.
You're partly right and partly wrong. These are indeed O(N) [or really, O(N+M)], assuming O(C) is constant, which it is if C is bound -- an often reasonable assumption.
These days, though, strings can sometimes be extraordinarily long, so it is an important point to keep in mind, in which case it's O(N*C) [or really O(N*C + M), assuming you optimize by hashing each string]. For example, it's not unusual to run a regular expression on arbitrary input, and the input can be many megabytes long -- in which case grepstrings that used to work just fine fail spectacularly. I learned this the hard way!