Comment by kortex

> (Btw, O(n log n) _is_ a polynomial runtime, and so is O(N) or even O(1). Though I can see that as a shorthand of notation you are excluding them.)

I mean yes, technically n^1 is a polynomial, but normally this is just called linear. You hit the nail on the head with the last sentence. Here I'm using polynomial to basically mean "n^k, k>1". From a NP vs P point of view, P is considered tractable. But from a "actually writing libraries" point of view, I think software developers consider O(n^2) "kinda bleh" if it can be at all avoided. Also developers tend to give much more weight to the actual coefficients / parallelism potential / practical runtime. Neural networks have superlinear bounds everywhere, but GPU goes brrr.

Brass tacks, sorting some tuples and diffing the rank then reducing strikes me as likely to be:

- pretty fast even in the naive implementation

- sorting is a well trodden field

- easy to write things like shaders for

- amenable to speculative execution

- amenable to divide and conquer

So that is what I mean by efficient.