An Interesting Sort
Consider the following algorithm for sorting a list:
- Shuffle the elements into random order
- Iterate through the list to check if it is sorted.
- If it isn't sorted, go back to step 1.
Assume that shuffling and checking the list are both linear operations in terms of the number of elements in the list.
Let O(f(n)) be the average case performance of this algorithm, where n is the number of elements in the list. What is f(4)/f(1) ?
For example: if the average case performance is O(\(n^2\)), then \(f(n) = n^2\), and \(f(4)/f(1) = 16/1 = 16\).