2 ms·
Hmm… what do you mean by faster? I guess you must mean something more nuanced than big-O. From a big-O perspective, sorting is typically O(n log n), but any a
by comex 5y ago
Hmm… what do you mean by faster? I guess you must mean something more nuanced than big-O. From a big-O perspective, sorting is typically O(n log n), but any algorithm that outputs n^2 values must take at least O(n^2) time, so adding O(n log n) makes no difference.
- kadoban 5y agoThe size of the output is n^2. So you do need at least that much effort. But it's not O(n lg n) to sort n^2 items, it'd be O(n^2) to just construct the output and then O(n^2 lg n) to sort it. So there is potentially a lg n to shave off there.