I am considering an algorithm for sampling from a collection without replacement. The algorithm I am considering is complex in that its runtime explodes under certain conditions. I am not concerned with the efficiency of the algorithm, but rather the maths concerned with determining big-O.
Consider a population or collection to be sampled from of size $N$ and the desired resulting sample size of $k$.
The algorithm I am considering is practically very similar to the one discussed in this question on stack overflow. The difference being that, where they consider a specific case of $k=N$, I am considering a more general case where $k\leq{N}$.
I have calculated that the expectation value for the number of iterations is: $\sum_{i=1}^{k}\frac{N}{N+1-i}.$
This can be rewritten to: $N\sum_{i=N+1-k}^{N}\frac{1}{i}.$
Is there a good approximation of this function?
I know that if the rewritten sum runs from $i=1$ to $N$, then a good approximation would be $N\ln{N}$. This is from the aforementioned question on stack overflow. This described big-O for the specific case where $k=N$.