Question

.
bogosort attempts to sort a list by shuffling the items in the list. If the list is unsorted after shuffling, we continue shuffling the list and checking until it is finally sorted.

1. What is the worst case run time for bogosort?
2. Why?
3. What is the average case run time for bogosort (Hint: think about a deck of cards )?
4. Why?

Answer 1

1) The worst case run time for bogosort is O(infinity).

2) The reason for this time complexity is that there exists no real upper bound for bogosort. The only thing that can be said about the big oh notation is O(infinity).

3) The average case run time for bogosort is O(n! * n).

4) We can shuffle n number of distinct elements in n! ways among which only one will produce a sorted order. The time taken for each shuffle will be O(n).

So, the average run time complexity for bogosort is O(n! * n).

Hope this helps.