4 ms·
How is it quadratic? You do 1000 checks every character in the haystack but that's still O(n)
by expenses3 1y ago
How is it quadratic? You do 1000 checks every character in the haystack but that's still O(n)
- burntsushi 1y agoThe worst case is that `std.mem.eql`[1] is executed at every position in the haystack, which gives you `O(n*m)` time complexity. Several substring search algorithms are `O(n)`. [1]: https://github.com/aarol/substr/blob/9392f9557de735929dfb79efa4fc88115341c65d/src/main.zig#L82 https://github.com/aarol/substr/blob/9392f9557de735929dfb79e...