Algorithm Analysis: Study the following sorting algorithm. SORT (A) // Assume there are n elements in A

1) for i = 0 to n 1

2) k = i + 1

3) for j = i + 2 to n

4) if A[k] > A[j]

5) k = j

6) if k i + 1

7) temp = A[i + 1]

8) A[i + 1] = A[k]

9) A[k] = temp

(a) (10 pts) Use the same method (longer approach described in lecture 2 week 1) as we used for analyzing Insertion-Sort to compute the running time T(n) of the above SORT algorithm. You may need to define variable such as ti or tj, similar to the variable tj we used in the lecture.

(b) (5 pts) Determine the worst case running time and the best case running time in terms of functions of n.