Comment by casta

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.