We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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!
Sparse Arrays
You are viewing a single comment's thread. Return to all 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!