3 ms·
You can do linear time complexity as long as the keys you are sorting don’t duplicate. The moment they do you can’t bean nlogn. Logn is basically the overhead o
by heavenlyblue 5y ago
You can do linear time complexity as long as the keys you are sorting don’t duplicate. The moment they do you can’t bean nlogn. Logn is basically the overhead of the worst case probability when keys overlap.
Just to be clear if you keys don’t duplicate then you are not resolving a sorting problem per se. It’s just a degenerate case of the problem which is obviously easy to resolve.
- Quekid5 5y agoI don't understand what you mean by duplicate here. Apply a Schwartzian Transform and there you go -- no duplicates.
- JohnHaugeland 5y agothe decorate sort undecorate is more expensive than the thing you're trying to save
- Quekid5 5y agoThat doesn't make sense. The Schwartzian Transform is linear time and cheap time-wise. Btw, I'm surprised nobody has objections about constants. The constants for the type of stuff 'discrimination' does are (apparently) really bad. Like really bad. ^ The above was a bit sarcastic. I know you're talking about straight up performance, but the problem there wouldn't be the Schwartzian Transform.