arguably it's O(N^2) in spacetime, because it's O(N) steps on O(N) hardware (N parallel units). You can imagine different hardware architectures taking O(1) st

arguably it's O(N^2) in spacetime, because it's O(N) steps on O(N) hardware (N parallel units). You can imagine different hardware architectures taking O(1) steps on O(N^2) parallel units or O(N^2) steps on O(1) unit(s), or anything in between.