Consider the given array InsertionSort algorithm and answer the following:

Algorithm InsertionSort(A):

Input: An array A of n comparable elements

Output: The array A with elements rearranged in increasing order

for i 1 to n1 do

{Insert A[i] at its proper location in A[0], A[1], ..., A[i1]}

cur A[i]

j i1

while j 0 and a[j] > cur do

A[j+1] A[j]

j j1

A[j+1] cur {cur is now in the right place}

A. Give a big Oh characterization, in terms of n, of the running time for the InsertionSort algorithm. Explain your answer.

B. Identify the best case and the worst case of the InsertionSort algorithm. Explain your answer.