# Making use of one function to recursively find n/3 of another

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?

• 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.

• [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. Oct 22, 2023 at 13:22