3 ms·
Couldn’t you construct a list of lists, where each is the output of one entry x + Y, and then just merge those lists like one would merge two sorted lists? (Bas
by bobthepanda 5y ago
Couldn’t you construct a list of lists, where each is the output of one entry x + Y, and then just merge those lists like one would merge two sorted lists? (Basically just popping off the smallest head at any given time)
You need to do the construction anyways (after all you need the elements of X+Y and you can’t get them without summing)
- karpierz 5y agoYou end up with N lists to merge, so to find the smallest head at each given time, you'd take log(N) steps. Given that you have N^2 elements, it would take a total of N^2 log(N) time, which is equivalent in time complexity to simply sorting a list with N^2 elements.
- bobthepanda 5y agoHm. that's fair. Just append them altogether and apply timsort, I guess, or some other sort that identifies runs well.