I'm 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:
- If n = 1 return A.
- p = ChoosePivot(A, n)
- B = Partition(A, n, p)
- Suppose p is the jth element of B (i.e., the jth order statistic of A). Let the “ﬁrst part of B” denote
its ﬁrst j − 1 elements and the “second part” its last n − j elements.
- If i = j, return p.
- If i < j, return Select(1st part of B, j − 1, i).
- 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?