2 ms·
in these days of modern CPUS with cache and branch prediction, O(n^2) often beats O(logn) because your data is tiny compared to the cost of all those cache miss
by bluGill 5y ago
in these days of modern CPUS with cache and branch prediction, O(n^2) often beats O(logn) because your data is tiny compared to the cost of all those cache misses and branch misses the seemingly faster algorithm creates. This doesn't apply when you data is large, but then you need parallel algorithms, and not in memory data (or just punt all your data to the sql server)
- AnimalMuppet 5y agoYeah. n = 3 more often than you expect. n <= 12 far more often than you expect. If you don't work at a FAANG, don't automatically assume that your data and algorithm need to squeeze the last O(logn) possible out of the algorithm.