Suppose that we read a sequence of $n$ numbers, one by one. How to find $k$'th smallest element just with using $O(k)$ cell memory and in linear time ($O(n)$). I think we should save first $k$ terms of sequence and when get the $k+1$'th term, delete a term which we sure that it cannot be the $k$'th smallest element and then save $k+1$'th term. So we should have an indicator that shows this unusable term in each step and this indicator should be update in each step quickly. I began with max; but it cannot update quickly; Means that if we consider max then in first deletion we miss the max and we should search for max in $O(k)$ and its cause $(n-k)\times O(k)$ time that it's not linear. Maybe we should save first $k$ terms of sequence more intelligently.How do I solve this problem?
Finding k'th smallest element from a given sequence only with O(k) memory O(n) time
data structures;search algorithms;quicksort
Create a buffer of size $2k$. Read in $2k$ elements from the array. Use  a linear-time selection algorithm to partition the buffer so that the $k$ smallest elements are first; this takes $O(k)$ time. Now read in another $k$ items from your array into the buffer, replacing the $k$ largest items in the buffer, partition the buffer as before, and repeat.This takes $O(k * n/k) = O(n)$ time and $O(k)$ space.