Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

According to Wikipedia, a linear congruential generator is defined by the recurrence relation below:

$X_{n} = (a \times X_{n-1} + c) \mod m$

where $0 < m, 0 \le a < m, 0 \le c < m, 0 \le X_{0} < m$ are integer constants that specify the generator.

If the value of $a$, $c$, $m$, $X_{0}$, and $n$ are given, can I determine the $k$-th smallest value ($1 \le k \le n$) of the set $\{X(0), X(1), ..., X(n)\}$ very fast? (faster than $O(k)$ - based by sorting algorithm)

share|improve this question
Since $n$ is fixed and $k \le n$, whatever algorithm you use will be $O(1)$. –  Robert Israel Oct 11 '13 at 15:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.