Bound on space for selection algorithm? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T07:31:17Z https://cs.stackexchange.com/feeds/question/2893 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/2893 11 Bound on space for selection algorithm? user834 https://cs.stackexchange.com/users/67 2012-07-24T03:19:59Z 2012-07-26T18:36:48Z <p>There is a well known worst case $O(n)$ <a href="http://en.wikipedia.org/wiki/Selection_algorithm">selection algorithm</a> to find the $k$'th largest element in an array of integers. It uses a <a href="http://en.wikipedia.org/wiki/Selection_algorithm#Properties_of_pivot">median-of-medians</a> approach to find a good enough pivot, partitions the input array in place and then recursively continues in it's search for the $k$'th largest element.</p> <p>What if we weren't allowed to touch the input array, how much extra space would be needed in order to find the $k$'th largest element in $O(n)$ time? Could we find the $k$'th largest element in $O(1)$ extra space and still keep the runtime $O(n)$? For example, finding the maximum or minimum element takes $O(n)$ time and $O(1)$ space. </p> <p>Intuitively, I cannot imagine that we could do better than $O(n)$ space but is there a proof of this?</p> <p>Can someone point to a reference or come up with an argument why the $\lfloor n/2 \rfloor$'th element would require $O(n)$ space to be found in $O(n)$ time?</p> https://cs.stackexchange.com/questions/2893/-/2896#2896 13 Answer by A.Schulz for Bound on space for selection algorithm? A.Schulz https://cs.stackexchange.com/users/2205 2012-07-24T08:56:25Z 2012-07-26T18:36:48Z <p>It is an open problem if you can do selection with $O(n)$ time and $O(1)$ extra memory cells without changing the input (see <a href="http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1641-05.pdf">here</a>). But you can come pretty close to this.</p> <p>Munro and Raman proposed an <a href="http://www.sciencedirect.com/science/article/pii/0304397595002251">algorithm for selection</a> that runs in $O(n^{1+\varepsilon})$ time while using only $O(1/\varepsilon)$ extra storage (cells). This algorithm leaves the input unchanged. You can pick any small $\varepsilon&gt;0$. </p> <p>At its core, Munro and Raman's algorithm works as the classical $O(n)$ algorithm: It maintains a <em>left</em> and <em>right</em> bound (called <em>filter</em>), which are two elements with known rank. The requested element is contained between the two filters (rank-wise). By picking a good pivot element $p$ we can check all numbers against the filters and $p$. This makes it possible to update the filters and decreases the number of elements left to check (rank-wise). We repeat until we have found the request element.</p> <p>What is different to the classical algorithm is the choice of $p$. Let $A(k)$ be the algorithm that solves selection for $\varepsilon=1/k$. The algorithm $A(k)$ divides the array in equally-sized blocks and identifies a block where many elements are, whose ranks are in between the filters (existence by pigeon-hole principle). This block will then be scanned for a good pivot element with help of the algorithm $A(k-1)$. The recursion anchor is the trivial $A(1)$ algorithm. The right block size (and doing the math) gives you running time and space requirements as stated above.</p> <p>Btw, the algorithms you are looking for, were recently named <em>constant-work-space algorithms</em>.</p> <p>I am not aware of any lower bound.</p>