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.
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!
Sparse Arrays
You are viewing a single comment's thread. Return to all comments →
Yes and this approach is actually O(n) unlike some comments above who have achieved this in O(n^2)
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!