3 ms·
Does "linear wrt A and linear wrt B" mean O(A*B) or O(A+B)?
by ridiculous_fish 7y ago
Does "linear wrt A and linear wrt B" mean O(A*B) or O(A+B)?
- gpm 7y agoIt means O(AB), but is carefully worded to not say (or suggest) it's not possible to do O(A+B) which is a subset of O(AB) ;) I'm not sure if it's possible to match regex with that time complexity, it looks like the implementation I referenced is O(AB). https://docs.rs/regex/1.3.1/regex/#untrusted-input https://docs.rs/regex/1.3.1/regex/#untrusted-input. (star symbol removed because hn decided to turn them into a block of italics)