adding equations ( through ( yields (nt( + + ( = the sum is about loge ( where is known as euler' constantso (no(log nn+ ( (no( log ( and so although this analysis seems complicatedit really is not--the steps are natural once you have seen some recurrence relations the analysis can actually be taken further the highly optimized version that was described above has also been analyzedand this result gets extremely difficultinvolving complicated recurrences and advanced mathematics the effect of equal elements has also been analyzed in detailand it turns out that the code presented does the right thing linear-expected-time algorithm for selection quicksort can be modified to solve the selection problemwhich we have seen in and recall that by using priority queuewe can find the kth largest (or smallestelement in ( log nfor the special case of finding the medianthis gives an ( log nalgorithm since we can sort the array in ( log ntimeone might expect to obtain better time bound for selection the algorithm we present to find the kth smallest element in set is almost identical to quicksort in factthe first three steps are the same we will call this algorithm quickselect let |si denote the number of elements in si the steps of quickselect are if | then and return the element in as the answer if cutoff for small arrays is being used and | <cutoffthen sort and return the kth smallest element pick pivot elementv partition {vinto and as was done with quicksort if <| |then the kth smallest element must be in in this casereturn quickselect( kif | |then the pivot is the kth smallest element and we can return it as the answer otherwisethe kth smallest element lies in and it is the ( | )st smallest element in we make recursive call and return quickselect( | in contrast to quicksortquickselect makes only one recursive call instead of two the worst case of quickselect is identical to that of quicksort and is ( intuitivelythis is because quicksort' worst case is when one of and is emptythusquickselect is not