top | item 45318678 (no title) casta | 5 months 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. discuss order hn newest TimorousBestie|5 months ago Yes, 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|5 months ago It's from the depth of the computation, not the work
TimorousBestie|5 months ago Yes, 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.
TimorousBestie|5 months ago
The algorithm with fewer data dependencies is O(N log N).
This is covered in more detail in the article.
gyrovagueGeist|5 months ago