[madsohm]

Also, they end up with a O(N*M) algorithm. They claim M is small, but it needs to be strictly smaller than logN if they want to be better than O(NlogN). A terabyte is 10^12. Thus log(N) is 12. They have 100 hidden neurons which is their M. So their algorithm isn't asymptotically faster, unless they go in N>10^100 with that amount of hidden neurons.

[hvidgaard]

For 32bit ints that in the order of 3.6e88 TBs.... To put that into perspective the visible universe contains an estimated of 10^82 atoms at most, so if a single atom contains 1 petabyte of data, and you want to sort all atoms and all or their data - this ML approach would be faster. I wish they had that discussion in the paper.

[titzer]

> A terabyte is 10^12.

It's 2^40, and log2(2^40) is 40.