How would you describe the running time of this sort, given a function sorted which returns True if the list is sorted that runs in O(n):
def sort(l):
while not sorted(l): random.shuffle(l)
Assume shuffling is perfectly random.
Would this be written in big-O notation? Or is there some other way of categorizing algorithms with random components?
Believe it or not, there's a wiki entry for this: http://en.wikipedia.org/wiki/Bogosort
Average case: O(N*N!)
Big-O notation assumes worst case scenario. In the worst case, this algorithm never terminates.
This Algorithm is called Bogosort. It is an instance of a class of Algorithms called Las Vegas Algorithms. Las Vegas Algorithms are Randomized Algorithms which always guarantee correct results but make no guarantees about the computing resources.
The time-complexity of Bogosort cannot directly be expressed in Bachmann-Landau Notation, because of its probabilistic nature. However, we can make a statement about its expected time-complexity. The expected time-complexity of Bogosort is O(n·n!).
The average case is indeed O( N N!):
Observe that there are exactly N! permutations of N elements. The probability of picking the right one is exactly 1/N!. Hence, by the strong law of large numbers, the expected number of sorts is N!.
Where does the other factor N come from? You have to check, at every step, what permutation you picked. That can be done linearly be comparing adjacent elements. Hence an extra factor N.
Comments above have indicated that O(g(n)) notation is "worst case":
1) That's not true. The definition of O(g(n)) is: f(n) is O(g(n)) if there exists some c,d such that f(n) < c * g(n) + d for sufficiently large n. There's nothing about "worst case". It just so happens that g(n) is a bigger function than f(n), but the pure mathematical definition says nothing about "case".
2) For randomized algorithms, it's pointless to do a "worst case" analysis anyway. You can come up with some execution that's going to be really bad.
3) The really bad executions occur on a set of measure 0 (A probabilist would say that they "almost surely" don't happen). They're actually impossible to observe.