2
$\begingroup$

Given an algorithm M that computes the median of an array A in O(n) time, describe an O(n) algorithm to repeatedly call M in order to find the element of rank n/3 in A.

This is a problem I am tasked with, and I have thought of a simple soln but I am not sure how to make it terminate:

To simply recursively call the M algorithm until I find the n/3. So it keeps halving until it finds the n/3 item.

However, since it is using recursion, how would I know when it has reached n/3 without calculating it prior?

$\endgroup$

1 Answer 1

1
$\begingroup$
  • Take the median and the median of the first half*.

  • In the subset between these, take the median and the median of the first half*.

Repeat the line above until the subset is a singleton.

The bounds between which the medians are taken are successively

$[0,n), [0,\frac n2)$

$[\frac n4,\frac n2), [\frac n4,\frac{3n}8)$

$[\frac{5n}{16},\frac{3n}8),[\frac{5n}{16},\frac{11n}{32})$

$\cdots$

The bounds converge to $\frac n3$, and the interval size each time decreases by a factor $4$. Hence the time complexity remains linear. ($n+\frac n2+\frac n4+\frac n8+\frac n{16}+\frac n{32}+\cdots=2n$)


*If the median algorithm does not rearrange the small and large elements on either side of the median respectively, you need to do it yourself. That does not impair the complexity.

$\endgroup$
1
  • $\begingroup$ [rearranging] the small and large elements on either side of the median [] does not impair the complexity [of O(n)]. That is one bold statement. $\endgroup$
    – greybeard
    Oct 22, 2023 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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