On Lower Bounds for Selection Problems
Let V i (n) be the minimum number of binary comparisons that are required to determine the i-th largest of n elements drawn from a totally ordered set. In this thesis we use adversary strategies to prove lower bounds on V i (n). For i = 3, our lower bounds determine V 3(n) precisely for infinitely...
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149426 |