randomized algorithm

We have already seen RSelect or Random Selection here. Now lets focus on DSelect. Though RSelect is good, and works in linear time, but it deterministically runs in O(n) time, even in worst case. But the downside is that it doesn’t runs as fast as RSelect, but its worst case is still better. Like in quicksort, we had it better than merge sort, but worst case of quicksort was worse than mergesort. [Read More]

Input - array A with n distinct numbers and a number i ∈ {1,2,…,n} Output : ith order statistic i.e. ith smallest element of the input array O(n log n) algorithm Apply mergesort/quicksort Return the ith element of sorted array So, we used reduction via taking the help of sorting algorithm. So this was the naive way as we would be to say, “Hey let’s sort it and then we can just pick out the ith one! [Read More]

Hoore cisca discovered it in 1961. Why quicksort? Definitely a greatest hit algorithm  Prevalent in practice O(n log n) time “on average” minimal extra memory needed (which gives it leverage over merge sort) The sorting problem Input: Array of numbers , unsorted. Eg. Output : Same numbers sorted in some order, say increasing order. Eg. Quicksort helps us solving this problem. What is quick sort? [Read More]