CODEWITHSUNDEEP
algorithm
i love stackoverflow
i love stackoverflow

Reputation: 1685

Given a list of songs on "shuffle", is it more efficient to randomly shuffle all the songs at once, or pick a random song each time?

What are the time complexities of

(1) randomly shuffling a list of length N?

(2) randomly choosing an item from a set of N items N times?

Upvotes: 0

Views: 587

Answers (2)

dstromberg
dstromberg

Reputation: 7177

Shuffling a list is O(n)

Choosing n things at random from a list of size n, is also O(n)

You're probably better off picking something at random on each play, because the list of songs is not necessarily going to remain the same forever. In such a case, the precomputation must be redone.

Upvotes: 1

Minigeek
Minigeek

Reputation: 36

Depends on your shuffle algorithm and intended behavior. For instance, iTunes shuffle creates an alternate playlist order when you shuffle, thereby shuffling all the songs immediately, but also creating a repeatable playlist order (if you listened to the playlist twice the same songs would follow each other), but if you wanted you could pick a new seed before each song and truly shuffle the tracks by picking when you start to play. Time-complexity, however, will essentially be identical for both, negligible in either instance.

Theoretically, however, they are both O(nr) time complexity (where r is the time complexity of your random number algorithm).

Upvotes: 2

Related Questions