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.

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

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