There are several steps where your method could (will) fail. Since you don't introduce any machinery for the hand, you imply an O(k^2) checking algorithm. You also imply an unsorted hand. If you generate the hand in random order, then you fall to an O(k*lg(k)) sort. "Sorted" is an implicit requirement that we initially omit, but revisit later, because introducing it early makes the discussion harder to follow.
If you try to introduce machinery like a hashtable, the next thing you might suggest, you violate an implicit O(1) additional space requirement, which I've grudgingly reintroduced to the more-formal description ("why is this here?"). This conversation keeps going, but other failure paths we leave unexamined.
For the cases where k > n/2, the "full table scan" portion is of course also linear in k.
We only need to consider values in the range 0 < k <= N/2. If k > N/2, we "pick the losers instead of winners" and that reduces k to that range.
The expected time E to pick k out of N, is N times the last k terms of H(N):
E(k) = N * (H(N) - H(N-k))
Applying the asymptote: E(k) ~ N * (γ + ln(N) - γ - ln(N-k))
= N * (ln(N) - ln(N-k))
We wish to determine its behavior as a function of k. Taking the derivative: dE/dk ~ N/(N - k)
which is positive and bounded above by 2 for 0 < k <= N/2: dE/dk <= 2
Using the fact that E(1) = 1, we have: E(k) <= 2k
So E cannot be worse than linear in k.
I don't think this is true!
First note that if you want to pick 98 values from 100, it is much simpler to instead decide which 2 to skip. Similarly when picking 75 out of 100 - better to just cross out 25. The hardest case is picking half: N/2 out of N, without replacement.
This is the Coupon Collector's problem, except we're stopping at half the coupons. We can use the analysis given in the Wikipedia page [1], except we only take the second half of the series.
This gives an expected time of
where H(X) is the Xth Harmonic number.In the asymptote this yields:
so the expected time of the "retry on duplicates" approach is linear in N. (Of course, the worst case is infinite, if you keep redrawing the same card.)edit: To complete the analysis, the requirement is that the answer be linear in k, the number of items selected. But we have k < N, so if we are O(N) we are also O(k) or better. So I think the argument works.
[1] https://en.wikipedia.org/wiki/Coupon_collector%27s_problem