3 ms·
No, you can’t even read the whole array in O(log^2(n)). It’s not possible to do better than O(n) without “cheating.”
by monochromatic 9y ago
No, you can’t even read the whole array in O(log^2(n)). It’s not possible to do better than O(n) without “cheating.”
- IAmLiterallyAB 9y agoI think the trick is you can run it in parallel. Which under ideal circumstances may give that kind of performance. But this is the first I've heard of this algorithm.