Lazy Larry was assigned to create a bubble sort algorithm, but he didn't have the time to do it properly. He designed the following algorithm instead:

For each iteration of the algorithm:

$\vphantom{1}$

Choose two distinct elements in the list uniformly at random.

Exchange the placements of those elements in the list.

Check to see if the list is now sorted. If it is, end the algorithm. Otherwise, do another iteration.

Lazy Larry tests his algorithm on the following list:

`capybara, dingo, aardvark, bandicoot`

What is the expected value of the number of iterations of Larry's algorithm to alphabetize the list (A to Z)?

×

Problem Loading...

Note Loading...

Set Loading...