python shuffle algorithm performance

Question

I was wondering about the time complexity of the shuffle function in the random Python library/module. Is it O(n) or is it less than that?

Is there a website that shows the time complexities of functions that belong to Python libraries?

Answer 1

You cannot shuffle a list in a completely random fashion in less than O(n).

The implementation of random.shuffle() uses the Fisher-Yates shuffle algorithm, which is easily seen to be O(n).