Consider the Bernoulli trial where a success is that a random permutation of a1, a2, . . . , an is ordered and a failure that a random permutation of a1, a2, . . . , an is not ordered. What is the probability of success? What is the probability of failure?
This assignment is an exercise in finding the average-case complexity of an
Rather than looking at how long an algorithm can run in the worst case as in worst-
case analysis, we are looking at how long an algorithm runs on average. This is done
by computing the average number of comparisons and operations executed until the
algorithm ends.
Bogosort is a sorting algorithm that orders a list in increasing order by taking the
list, checking to see if the list is ordered increasingly, if the list is not ordered increasingly
then the list is randomly shuffled, and then repeating this process until the list is ordered
increasingly.
Expressed in pseudocode:
Algorithm 1 Bogosort
Require: list: a1, a2, . . . , an of real numbers
Ensure: list is sorted in increasing order
1: procedure bogo(list)
2: while not sorted(list) do ▷ Checks to see if list is sorted
3: shuffle(list) ▷ Shuffle the current list if not sorted
4: end while
5: end procedure
Problem: Consider the Bernoulli trial where a success is that a random permutation of
a1, a2, . . . , an is ordered and a failure that a random permutation of a1, a2, . . . , an
is not ordered. What is the probability of success? What is the probability of
failure?
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
