3 ms·
With worst case of O(n^2) though? In hindsight it should be possible, since if we use insertion sort, we also get best of O(n) and worst of O(n^2). Though quick
by mcmoor 3mo ago
With worst case of O(n^2) though? In hindsight it should be possible, since if we use insertion sort, we also get best of O(n) and worst of O(n^2). Though quick select do have average O(n).
- dgacmu 3mo agoDepends if you're talking theory or practice. introselect is worst case O(n) but a lot of implementations implement it with avg case O(n) and worst case O(log n). Median of medians is worst case O(n) but it's slow so mostly avoided.
- dgacmu 3mo ago* introselect implementation often worst case n log n, typo