Consider the following algorithm:

Sort(A, n) {

for i = 2 to n {

key = A[i]

j = i - 1;

while (j > 0) and (A[j] > key) {

A[j+1] = A[j]

j = j - 1

}

A[j+1] = key

}

}

a) What type of sorting does is perform? Why?

b) Show the cost for executing each line in the algorithms then further compute the T(n) expression for the algorithm.

c) What is the Upper bound expression for the algorithm? Explain your answer.

d) What is the Lower bound expression for the algorithm? Explain your answer.