Complexity of Enum functions

I wanted to know what is the time complexity of Enum.random and Enum.shuffle.

More specifically i wanted to figure out if I want to select 50 random values from a possible set of 10,000 values, will it be faster to shuffle the list and then take first 50 elements or select random elements 20 times

The shuffle implementation is straightforward. It creates assigns a random number to each list element and then sorts them and returns the result: Enum.random depends on Enum.take_random which seems to creates a map with all the elements and takes a few of them.

To answer your question, you should run a few benchmarks using benchee to decide which one to use. If you want multiple random elements use Enum.take_random(enumerable, count) instead of running Enum.random multiple times.

Random on a range is O(1), all other enumerables are O(n).

So 20 times Enum.random() will still run in constant time but Enum.shuffle and then Enum.slice() will take O(n). Am I correct?

If and only if you use a Range as input for Enum.random/1 you will get get your result in constant time.

But you also have to remember that there are differences between both versions of code:

def pick20a(enum) do
  |> (_) -> Enum.random(enum) end)

def pick20b(enum) do
  |> Enum.shuffle()
  |> Enum.take(20)

pick20a/1 might return some elements multipletimes, while pick20b/1 won’t, also pick20b will never return more elements than your input has:

iex(2)> M.pick20a(1..10)
[3, 4, 3, 10, 5, 10, 9, 1, 8, 9, 1, 10, 3, 7, 3, 8, 4, 5, 5, 7]
iex(3)> M.pick20b(1..10)
[7, 3, 5, 1, 6, 2, 9, 8, 4, 10]