top | item 44863617 (no title) expenses3 | 6 months ago How is it quadratic? You do 1000 checks every character in the haystack but that's still O(n) discuss order hn newest burntsushi|6 months ago The 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/9392f9557de735929dfb79e...
burntsushi|6 months ago The 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/9392f9557de735929dfb79e...
burntsushi|6 months ago
[1]: https://github.com/aarol/substr/blob/9392f9557de735929dfb79e...