Chapter 2 Section 2 Exercises Intro to Algorithms CLRS (3rd)

2.2-1 Express the function n^3/1000-100n^2-100n+3 in terms of theta-notation. Solution: theta(n^3)

2.2-2 Write an algorithm for selection sort. What loop invariant does this algorithm maintain? Why does it need to run for only the first n-1 elements, rather than for all n elements? Give the best-case and worst-case running times of selection sort in theta-notation. Solution:

The loop invariant is the sorted sub-array A[1,..,i]. The last element is trivially sorted. The best case is pre-sorted, the worst case is anti-sorted.

2.2-3 Consider linear search again. How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be an element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in theta-notation? Solution: Since it is equally like that the element is in the first or second half subarray, half of the elements will be searched on average. in the worst case, all of the elements will be searched. Both have linear run times n/2 and n, so T(n)=theta(n).

2.2-4 How can we modify any algorithm to have a good best-case running time? Solution: Assign a correct pre-calculated output for a selected input and have this checked (in constant time). Usually not useful.