Selection algorithm: Difference between revisions

Revision as of 13:51, 26 March 2013

Revision as of 23:23, 29 March 2013

Line 142:

The median-calculating recursive call does not exceed worst-case linear behavior because the list of medians is 20% of the size of the list, while the other recursive call recurses on at most 70% of the list, making the running time

:<math>T(n) \leq T(n \cdot 2/510) + T(7n \cdot n7/10) + O(n).</math>

The O(''n'') is for the partitioning work (we visited each element a constant number of times, in order to form them into n/5 groups and take each median in O(1) time).