Selection algorithm: Difference between revisions

Revision as of 12:54, 2 January 2018

Revision as of 22:34, 20 February 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''[?reference].

== Space complexity ==