3 ms·
How's the prefix sum on a single thread O(N log(N))? Isn't it trivially O(N)? It's just a for loop.
by casta 1y ago
How's the prefix sum on a single thread O(N log(N))? Isn't it trivially O(N)? It's just a for loop.
- TimorousBestie 1y agoYes, but for loop comes with all those data dependencies that prevent it from being parallelized trivially. The algorithm with fewer data dependencies is O(N log N). This is covered in more detail in the article.
- gyrovagueGeist 1y agoIt's from the depth of the computation, not the work