Comment by peri-cl

> "As we get into higher dimensional spaces, things get weird really fast."

The geometric problem of computing a d-dimensional Pareto set of cardinality n

https://en.wikipedia.org/wiki/Maxima_of_a_point_set

has a truly weird property not covered by the computational complexity discussion on that page. It says there's an algorithm achieving O(n log(n)^(d-3) log log n), which is true and also a lie. The algorithm that achieves that asymptotic form is a galactic algorithm; and not an ordinary one in the sense of "has a large constant multiplicative factor", but one with this property (I've never found any other algorithm which exhibits it):

The runtime is within a bounded constant factor of n^2, for all n up to some critical N whose size is exponential in d (I think it was exactly 2^d or something).

I.e. the runtime has "two shapes": it's purely quadratic up to a galactically-large constant, and thereafter has a transition into to a slower function. The asymptotic version in the textbooks isn't achievable in the real world (for all but very small dimension).

There's an elementary proof using generating functions.

edit to add: If anyone's curious about it, a simplified version of the recurrence relation that's enough to exhibit this behavior (you can instantly see it if you graph this numerically) is

    f(n,d=0) = 1
    f(n=1,d) = 1
    f(n,d)   = n + 2f(⌊n/2⌋, d) + 2f(⌊n/2⌋, d-1)