Big-O complexity of random.choice(list) in Python3

complexity-theory, python, python-3.x, random

Solution

`O(1)`. Or to be more precise, it's equivalent to the big-O random access time for looking up a single index in whatever sequence you pass it, and `list` has `O(1)` random access indexing (as does `tuple`). Simplified, all it does is `seq[random.randrange(len(seq))]`, which is obviously equivalent to a single index lookup operation.

An example where it would be `O(n)` is `collections.deque`, where indexing in the middle of the `deque` is `O(n)` (with a largish constant divisor though, so it's not that expensive unless the `deque` is reaching the thousands of elements range or higher). So basically, don't use a `deque` if it's going to be large and you plan to select random elements from it repeatedly, stick to `list`, `tuple`, `str`, `byte`/`bytearray`, `array.array` and other sequence types with `O(1)` indexing.

Problem

Original source