Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Im trying to understand the basic concepts of algorithms through the classes offered at Coursera (in bits and pieces), I came across the deterministic linear time selection algorithm that works as follows:

Select(A,n,i)
(0)  If n = 1 return A[1].
(1)  p = ChoosePivot(A, n)
(2)  B = Partition(A, n, p)
(3)  Suppose p is the jth element of B (i.e., the jth order statistic of A). Let the “first part of B” denote
its first j − 1 elements and the “second part” its last n − j elements.
(3a)  If i = j, return p.
(3b)  If i < j, return Select(1st part of B, j − 1, i).
(3c)  Else return Select(2nd part of B, n − j, i − j).

And sorts the array internally in the ChoosePivot subroutine to calculate the median of median using a comparison based sorting algorithm. But isnt the lower bound on comparison based sorting O(nlogn)? So how would it be possible for us to acheive O(n) for the entire algorithm then? Am I missing something here?

share|improve this question
    
Are you sure that's what ChoosePivot does? –  AakashM May 17 '12 at 9:47
    
Yeah ChoosePivot computes the median of medians of the original array for which it employs comparison based sorting, which theoretically has a worst case of O(nlogn) if Im not mistaken –  KodeSeeker May 17 '12 at 9:55

1 Answer 1

up vote 5 down vote accepted

And sorts the array internally in the ChoosePivot subroutine to calculate the median of median using a comparison based sorting algorithm.

This is the incorrect premise (you are right that if we did do a comparison-based sort, we couldn't be linear). The point of median-of-medians is that it is linear - you don't need to sort the whole set if all you want is the median. See proof of O(n) running time on wikipedia for more detail.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.