4 ms·
Yes, but if something is O(m*n) and m <= n (which is the case in string search), then it's also O(n^2). On the other hand, since m can be of the order of, say,
by xyzzyz 12y ago
Yes, but if something is O(m*n) and m <= n (which is the case in string search), then it's also O(n^2). On the other hand, since m can be of the order of, say, n/2, it's not too confusing to say that naive string search is O(n^2), since it's actually Theta(n^2).
- alayne 12y agoYes, you are right of course. I really just meant that "in practice" the growth of the string length (m) varies independently and common cases behave more like O(n) than O(n^2). Also that naive search is probably heavily optimized with SSE assembly instructions and cache tuned. I have implemented several of these algorithms in C and it is difficult to impossible to beat C's strstr consistently with a simple implementation, even on cases that start to make the naive algorithm really inefficient. You'd most likely need a hybrid approach to make a good general purpose string search function that is effective across many domains.