[willvarfar]

your random number function might return the same number multiple times? So to choose k random but unique numbers you may have to call the random number function more than k times?

Of course my intuition would be that you can do a random shuffle and then take the first k, which is O(N). So I might be misunderstanding.

[chopin]

Is there a O(n) shuffling algorithm? In place, I don't think so.

[tialaramex]

Um, the "Knuth Shuffle" aka "Fisher-Yates" ?

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

[minitech]

You can do that for O(N), but the problem can be solved in O(k).