3 ms·
TL;DR: Scala doc claims that their algorithm is O(log32(N)), where N is not greater than 2^31, so it's O(6)=O(1) -- "effectively constant". Author claims that
by deepsun 9y ago
TL;DR:
Scala doc claims that their algorithm is O(log32(N)), where N is not greater than 2^31, so it's O(6)=O(1) -- "effectively constant".
Author claims that then all real-world algorithms are constant, for example bubble sort is O(N^2), where N is not greater than 2^31, so it's O(2^62)=O(1) -- also "effectively constant".
- benlorenzetti 9y agoWell put! Taking author's basic proposition to its logical conclusion shows that faulting Scala for this is wrong. Scala has illuminated the author to a pedantic dissonance in academia: in this case, that true asymptotic analyses should be using O(logn) instead of O(1) for random memory access. Hence why algorithms like Hoare's quicksort are so fast, they actually are Theta(nlogn) in practice because linear memory access looks like O(1) on modern machines. (but again pedantically it is probably still O(logn) from gate depth of multiplexing/demultiplexing the architecture's pointer size.) Edit: Remembering that O((logn)^2) = O(logn), I suppose the author is probably correct.