# Using “incremental algorithms” to find the $k^{th}$ smallest number

This is what I vaguely understand of what an "incremental algorithm" is - say one such for calculating the $k^{th}$ smallest number for a given sequence of elements $x_1, x_2,...,x_n$ then after the algorithm has seen the elements $x_1, x_2, x_3, ... , x_{i-1}$ it has either,

(1) computed the $k^{th}$ smallest element till then or

(2) it has computed a some other invariant from which the $k^{th}$ smallest element can be computed and this invariant is updated when it sees $x_i$.

• How is this different from a "greedy algorithm" ?

• Can someone explain actual algorithm for this and what is its worst case and or expected running time?

• Further it seems that if the algorithm randomly permutes the given sequence then the expected running time can be upper bounded by $n + O(k \log(n/k))$. Can someone explain what this is?

What does it technically mean to choose a permutation randomly and how is this actually implemented?

• Does being "upper bounded by $n + O(k \log(n/k))$" means the same as having "complexity in $O(n+k \log(n/k))$". If no, what is the difference? If yes why this weird mix of notations? – babou Oct 19 '14 at 11:00
• @babou Can you explain whatever you think is the right answer? :) – guest Oct 19 '14 at 17:58
• Too many things I do not understand in your question (algorithmics is not my field), so I am not sure what the problem really is. But to get the $k^{th}$ smallest number in a list of $n$, I would think that it can be done in linear time with a max-heap of size $k$. Regarding the notation for the upperbound, I do not know. People abuse complexity notation all the time, and what they mean is anybody's guess. The problem is that $O(n+k\log(n/k))=O(n)$ when $k$ is constant, if I am not mistaken, so that I wonder what is intended. I do not like to answer when I do not get the meaning of things. – babou Oct 19 '14 at 23:24