4 ms·

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 terab

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 8y ago
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 8y ago
> A terabyte is 10^12. It's 2^40, and log2(2^40) is 40.