The single-thread performance of the parallel prefix sum that they use is O(N log N), so the improvement from that to O(log N) on N threads is not as surprising.
The way the headline is written, it sounds like Amdahl’s law was violated. It wasn’t, of course.
The way the headline is written, it sounds like Amdahl’s law was violated. It wasn’t, of course.