There is an O(n) worst case algorithm for finding the kth smallest element. See http://en.wikipedia.org/wiki/Select_kth_element#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm. Dave
On Dec 8, 10:26 am, jai gupta <sayhelloto...@gmail.com> wrote: > @coolfrog > the question never asked u to find thm in order of thier distances. > Correct me if i m wrong! > > find the distances in O(n) > > now using the partitioning process of quicksort. > Dividing the array into two parts: > Now if the Length of the first part is less than or equal to i we have to > now make our search into one of the subarrays > > In average: > T(n)=T(n/2)+O(n) > > which satisfies T(n)=O(n) > > though in worst case this algorithm can take u to O(n^2) > but in average case it takes u to O(n) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
