3 ms·
What structure should there be for nlogn solution to be applicable?
by qumpis 4y ago
What structure should there be for nlogn solution to be applicable?
- cperciva 4y agoThe issue isn't structure but rather density. If you have N values ranging from -M to M, the "obvious" solution is O(N^2) and the convolution us O(M log M). So if you have lots of values within a narrow range the convolution wins.