Selection algorithm: Difference between revisions

Revision as of 19:41, 23 June 2013

Revision as of 13:31, 17 July 2013

Line 144:

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/10) + T(n \cdot 7/10) + O(c \cdot n).</math>

The O(''n'') term ''c 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).

From this, using induction, one can theneasily show that

:<math>T(n) \leq c10 \cdot nc \cdot (1 + (9/10) + (9/10)^2 + \cdots)n \in O(n).</math>

being c the coefficient of n of the partitioning work cost bound.

=== Important notes ===