|
|
|
|
|
|
by zahlman
485 days ago
|
|
|
>This is based on a flawed analysis assuming rainbow endpoints will be evenly distributed I guess you know this, but we don't need to do any complicated analysis to disprove such a big-O for a comparison-based sort. It's a well known information-theory result: each comparison can remove at most O(1) entropy, while the initial state has O(n lg n) entropy because that's how log(N!) grows (https://en.wikipedia.org/wiki/Stirling%27s_approximation). |
|
|