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?

  • $\begingroup$ 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? $\endgroup$ – babou Oct 19 '14 at 11:00
  • $\begingroup$ @babou Can you explain whatever you think is the right answer? :) $\endgroup$ – guest Oct 19 '14 at 17:58
  • $\begingroup$ 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. $\endgroup$ – babou Oct 19 '14 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.