11.1.8. Recursive Time Complexity

Now, there is another way of looking at selection sort. So, remember we said, that we start by finding the minimum element moving into the front and then doing the same thing. Whenever you say do the same thing it is useful to think of this as a recursive algorithm just to convince yourself, that what you are doing is correct.

In this chunk, we discuss the recursive perspective on selection sort. In recursive algorithms, a function calls itself to solve smaller instances of the same problem. Here, we start by finding the minimum element in the unsorted part of the array. Once the minimum is found and moved to the front, we recursively call the same selection sort function on the remaining unsorted elements. This shifts our focus to smaller and smaller segments of the array until we reach a single element, which is inherently sorted.

Think of this like organizing a set of books. You first take one book, which is the smallest in height and put it on a shelf. Then, you recursively apply the same process to the remaining books. Each step takes one book from the unsorted pile until all books are sorted by height.

So, in order to sort in general A from some position i to n minus 1, what we do is we find the minimum value in the segment, that is, from A to i to A i minus 1 and move it to the beginning, which is A i.

Here, we specify the steps taken in the recursive implementation. The selection sort is performed on a segment of the array from index 'i' to the end. We first determine the minimum value within this segment, then we place that minimum at the 'i' position. Following this action, the next step is to recursively apply selection sort on the rest of the elements, starting from 'i + 1'. This process continues until we reach the last element, at which point the algorithm recognizes it as sorted.

Imagine a teacher sorting student exam papers one at a time by scores. The teacher picks the lowest score from the unsorted pile and puts it at the front. After each pick, the remaining unsorted papers are dealt with in the same manner, recursively reducing the number of papers until only one is left.

So, suppose t n is the number of steps you need to run selection sort in length n, ok. So, the first thing is, it requires n steps in order to find the minimum and move it to the beginning...

In this chunk, we analyze the time complexity of recursive selection sort. Denote 't(n)' as the time taken to sort an array of length 'n'. The algorithm first requires 'n' operations to find the minimum, then it recursively calls itself on 'n-1'. Expanding this recursively leads to a total time of 'n + (n-1) + (n-2) + ... + 1', which sums up to 'O(n^2)', meaning the time complexity remains quadratic as previously established for the iterative version.

To better understand this, imagine a scenario where you line up guests by height at a party. Every time you check the lineup to find the shortest guest, it takes time proportional to the number of guests currently unsorted. By removing each guest iteratively, the sorting task grows cumulatively until all guests are sorted, demonstrating how the quadratic time complexity arises.

--