Selection algorithm: Difference between revisions

Revision as of 23:18, 15 April 2018

Revision as of 23:38, 15 April 2018

Line 77:

:<math>W_{t}(n) \leq n - t + \sum_{n+1-t < j \leq n} \lceil{\log_2\, j}\rceil \quad \text{for}\, n \geq t</math>

This bound is achievable for ''t''=2 but better, more complex bounds are known for larger ''t''.{{citation needed|date=April 2018}}

== Space complexity ==