in (ntime for any value of moreoverthe technique we use to achieve this result involves an interesting algorithmic design pattern this design pattern is known as prune-and-search or decrease-and-conquer in applying this design patternwe solve given problem that is defined on collection of objects by pruning away fraction of the objects and recursively solving the smaller problem when we have finally reduced the problem to one defined on constantsized collection of objectsthen we solve the problem using some brute-force method returning back from all the recursive calls completes the construction in some caseswe can avoid using recursionin which case we simply iterate the prune-and-search reduction step until we can apply brute-force method and stop incidentallythe binary search method described in section is an example of the prune-andsearch design pattern randomized quick-select code fragment randomized quick-select algorithm in applying the prune-and-search pattern to the selection problemwe can design simple and practical methodcalled randomized quick-selectfor finding the kth smallest element in an unordered sequence of elements on which total order relation is defined randomized quick-select runs in (nexpected timetaken over all possible random choices made by the algorithmand this expectation does not depend whatsoever on any randomness assumptions about the input distribution we note though that randomized quick-select runs in ( time in the worst casethe justification of which is left as an exercise ( - we also provide an