| | | Complexity Proof for recSelSort |
Claim: recSelSort(n-1,elts) (i.e, on n elements) involves n*(n-1)/2 comparisons of elements of array.
Base: n = 0 or 1, 0 comparisons and n*(n-1)/2 = 0.
Induction hypothesis: Suppose recSelSort(k-1,elts) takes k*(k-1)/2 comparisons for all k < n.
Induction step: Show that it's true for n as well.
Look at algorithm: Run algorithm on recSelSort(n-1,elts). Therefore, last = n-1.
Go through for loop "last" = n-1 times, w/ one comparison each time through.
Thus n-1 comparisons. The only other comparisons are in the recursive call: recSelSort(last-1,elts) where last = n-1.
But by induction (since last < n), this takes last*(last-1)/2 = (n-1)*(n-2)/2 comparisons.
Therefore, altogether we have (n-1) + (n-1)*(n-2)/2 = (n-1)*2/2 + (n-1)*(n-2)/2 = (n-1)*(2 + n-2)/2 = (n-1)*n/2 = n(n-1)/2 comparisons.
Finished proof.
Therefore recSelSort takes O(n2) comparisons.
| | | Complexity Proof for recSelSort |