[dgacmu]

Depends 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]

* introselect implementation often worst case n log n, typo