When looking through a few questions at StackOverflow¹ that all ask for algorithms to select k distinct random numbers out of N, I've become confused about how to compare the answers in terms of time and space complexity.
- each algorithm has two parameters, N and k
- and returns k elements
In terms of Big O notation, all the algorithms worth speaking of are O(N) overall.
But there are still major differences between them:
- Some require ~k steps while others ~N
- Some can return elements one by one while others only return them all at the end.
- Most require all the k (or even N) elements to be present in memory at once, but some are able to return each one in sequence and discard it.
Now to unambiguously put these distinctions when describing each algorithm's complexity? More specifically, I'm interested in the standard way it is done in formal papers so as not to reinvent the wheel.
¹https://stackoverflow.com/questions/196017/unique-non-repeating-random-numbers-in-o1/16097246, https://stackoverflow.com/questions/158716/how-do-you-efficiently-generate-a-list-of-k-non-repeating-integers-between-0-and-n, https://stackoverflow.com/questions/2394246/algorithm-to-select-a-single-random-combination-of-values, https://stackoverflow.com/questions/54059/efficiently-selecting-a-set-of-random-elements-from-a-linked-list