## Friday, June 5, 2015

Problem

Moving forward, we are going to do something cool with random numbers. This problem is about generating a random selection without replacement. The original algorithm used a list to represent the remaining items, so every time we need to pick an item it takes $O(n)$ time, and therefore a total of $O(kn)$ time, if $k = n$, then we have $O(n^2)$ time. With the current version, I used an AVL tree to represent the items, so it takes an overall $O(k \log n)$ time for the selection, but remember we need to populate the tree at the first place, so an overall $O(n \log n)$ time.