python shuffle algorithm performance

python performance time-complexity shuffle
Saher Ahwal picture Saher Ahwal · Feb 21, 2012 · Viewed 8.6k times · Source

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

Sven Marnach picture Sven Marnach · Feb 21, 2012

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).

Related questions

How can you profile a Python script?

Project Euler and other coding contests often have a maximum time to run or people boast of how fast their particular solution runs. With Python, sometimes the approaches are somewhat kludgey - i.e., adding timing code to __main__. What …

Read More
How efficient/fast is Python's 'in'? (Time Complexity wise)

In Python, what is the efficiency of the in keyword, such as in: a = [1, 2, 3] if 4 in a: ...

Read More
How to improve performance of this code?

Thanks to some help from people here, I was able to get my code for Tasmanian camels puzzle working. However, it is horribly slow (I think. I'm not sure because this is my first program in Python). The example run …

Read More