4 ms·

Interesting. One thing they leave implicit is the amount of work that parsing requires. The result is that you can parse in time O(log n) if you use O(n) proc

Interesting. One thing they leave implicit is the amount of work that parsing requires. The result is that you can parse in time O(log n) if you use O(n) processors, so parsing requires O(nlogn) work. (This is probably to be expected.) I think this means that, if you have o(n) strings to parse, you're better off with the good old DFA solution which uses O(n) work and parsing the different strings in parallel.

gue5t 8y ago
Yes, given no context one assumes serial computation, where work and depth are identical. An O(log n)-work parser would be astounding, because it's impossible--it would have to ignore effectively all of the input. This isn't clickbait because it's a real article and a good technique, but it's definitely exaggerating the surprise factor with misleading phrasing.