Lazy Larry's Random Algorithm

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...