17

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?

Mark Amery
  • 143,130
  • 81
  • 406
  • 459
Saher Ahwal
  • 9,015
  • 32
  • 84
  • 152
  • 2
    For your second question - http://wiki.python.org/moin/TimeComplexity – Alex L Feb 21 '12 at 02:11
  • 1
    @Alex: considering the only library in that list is `collections`, not quite what OP is asking for, I think. – Wooble Feb 21 '12 at 02:36
  • 1
    @Wooble It's a wiki, so it may not be limited to just `collections` in the future. (Upon re-reading, it seems like this is for CPython, but at least an interesting reference. It may inspire someone to create an equivalent wiki page for `random`, and other libraries) – Alex L Feb 21 '12 at 05:05

1 Answers1

25

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

Sven Marnach
  • 574,206
  • 118
  • 941
  • 841
  • Thank you! I guess I need my own random function (not completely random i guess) – Saher Ahwal Feb 21 '12 at 02:09
  • @Saher: can you even conceive of a method of shuffling a list in place that's better than O(n)? – Wooble Feb 21 '12 at 02:39
  • I haven't thought that through but what I meant is basically for my purposes for the algorithm I am writing I can just shuffle the first 4 to 5 items and choose the first one, it is not crucial. – Saher Ahwal Feb 21 '12 at 03:39
  • Now that I think more about it. There is no way you can do better than O(n) since you have to encounter every list element at most once. – Saher Ahwal Feb 21 '12 at 03:40
  • 6
    @Saher: If you only choose the first one, maybe all you need is `random.choice()`? – Sven Marnach Feb 21 '12 at 04:20