• + 0 comments

    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!