> choosing k elements from 1..n uniformly at random Can you clarify the problem? k elements uniformly at random, independently, with replacement, sounds like

> choosing k elements from 1..n uniformly at random Can you clarify the problem? k elements uniformly at random, independently, with replacement, sounds like it’s trivially O(k), or perhaps O(k log n) if n is so big that you need O(k log n) bits to merely represent the answer. (Those logs are pesky and can appear and disappear in different models of computation!) Maybe you mean k distinct elements? Off the top of my head, if n is not huge (n = O(k), or more concretely, n < ck for your choice or c > 1, and I would probably start with 2 if I were implementing this), I would make an array of all the elements and draw k of them using any of a number of straightforward algorithms. (Fischer-Yates, for example, but I admit I had to look up the name.) For larger n, make a hash table to store the elements selected so far. Now repeat k times: choose an element at random and retry if it’s a duplicate. Then add it to the hash table and continue. Each iteration takes at most 1/c tries on average, so the overall expected time is O(k). (For n < ck, the last few draws may retry quite a lot.) Thinking of this as sorting seems odd, but I admit I’m thinking about this in 2023, not the 1970s :)