We have An array of $3n$ elements. we want to Find $x$ and $y$ for array of $3n$ numbers such that 1/3 are less than $x$. 1/3 between $x$ and $y$ and 1/3 greater than $y$. We can solve this problem of $M(n)$ space and $T(n)$ time complexity. We want to find $M(n)$ and $T(n)$ as functions of $n$. Note that $x$ and $y$ are not in array. for example if the array is $1 , 2 , 3, 4 , 5 ,6$ we can have $x=2.5$ and $y=4.5$. Also $x$ and $y$ are obviously not unique and we just want one number for each of them that satisfy the conditions. The array is not necessarily sorted.
For this problem, I was thinking of using order statistic and find $n$ and $n+1$ and $2n$ and $2n+1$ elements. But the problem seems odd to me. I know Selection algorithm is $O(n)$ but this problems seem more complex than just saying that.
It is the problem of a quiz of DS course (Of an Iranian University) but it seems like it is from a reference book. I want to know the answer of this question or reference to know what the question really wants and maybe finding the answer this way.
