Yeah, this has worse complexity than Pearson. However, it's not competing on complexity. The point of it is to detect general dependencies, where Pearson only

Yeah, this has worse complexity than Pearson. However, it's not competing on complexity. The point of it is to detect general dependencies, where Pearson only detects linear ones (cases where Y is completely determined by X but their Pearson correlation is 0 are trivial to construct). The "linear" in linear dependency isn't the same as the "linear" in linear complexity here, but it doesn't seem surprising for an algorithm that can detect more general dependencies to have worse than linear performance (and nlogn is pretty much the next best). In the absence of a known algorithm with the same properties and better complexity, it doesn't seem unreasonable to call it "computationally efficient" when it comes with a complexity sufficient for most uses, rather than say quadratic or exponential.