Solution Found!
Defining the basic operation as the comparison of list
Chapter 3, Problem 16(choose chapter or problem)
Defining the basic operation as the comparison of list elements and ignoring the amount of work required to exchange list elements, write a recurrence relation for the amount of work done by selection sort on an n-element list. (Hint: Use the result from Exercise 15.)
Questions & Answers
QUESTION:
Defining the basic operation as the comparison of list elements and ignoring the amount of work required to exchange list elements, write a recurrence relation for the amount of work done by selection sort on an n-element list. (Hint: Use the result from Exercise 15.)
ANSWER:Step 1 of 2
If there is only 1 element in the list, no comparisons need to be made
If there is n elements in the list , n-1 comparisons have to be made to find the maximum element .
If is the number of comparisons needed to sort the n-element list , then the number of those comparisons equals the number of comparisons needed to sort the elements list (which is ) plus