finding smallest k elements in array in O(k)
Preprocess the array of $n$ values in time $O(n)$:


$i\leftarrow n$
while $i&gt;2$

Compute the median $m$ of $A[1..i]$ in time $O(i)$
partition $A[1..i]$ into $A[1..i/2-1] \leq m$ and $A[i/2+1..i]\geq m$ in the same time.
$i \leftarrow \lfloor i/2 \rfloor$



The total precomputation time is within $O(1+2+4+...+n)\subseteq O(n)$

Answer a query for the $k$ smallest elements in $A$ in time $O(k)$:


$l\leftarrow \lfloor \log_2 k \rfloor$
select the $(k-2^l)$th element $x$ of $A[2^l..2^{l+1}]$ in time $O(2^l)\subseteq O(k)$
partition $A[2^l..2^{l+1}]$ by $x$ in the same time


$A[1..k]$ contains the $k$ smallest elements.

References:


In 1999, Dor and Zwick gave an algorithm to compute the median of $n$ elements in time within $2.942 n + o(n)$ comparisons, which yields an algorithm to select the $k$th element from $n$ unordered elements in less than $6n$ comparisons.