Assertion: algorithm's complexity | /r/HasProperty | geometric series
Facets:
Source sentences:
text: This is because Quickselect is a divide and conquer algorithm, and using the median at each pivot means that at each step the search set decreases by half in size, so the overall complexity is a geometric series times the complexity of each step, and thus simply a constant times the complexity of a single step, in fact 2 = 1 / ( 1 − ( 1 / 2 ) ) {\displaystyle 2=1/(1-(1/2))} times (summing the series).