Content deleted Content added
Gave explicit time bound for minimum-based selection |
m Link fix |
||
Line 100:
What makes this a good pivot? Note that it is both less and greater than half the elements in our list of medians, or ''n''/10 elements. Moreover, each of these elements is a median of 5, and so is both less and greater than 2 others outside the block, or 2(''n''/10) elements. Thus the median we chose splits the elements somewhere between 30%/70% and 70%/30%, which is more than good enough to assure worst-case linear behavior of the algorithm.
The trick, however, is ensuring that the added recursive call does not destroy this worst-case linear behavior. This is because the list of medians is 20% of the size of the list, and the other recursive call recurses on at most 70% of the list, so we have this [[
T(''n'') ≤ T(''n''/5) + T(7''n''/10) + O(''n'')
| |||