Binary_InsertionSort (A, n) 1) for j 2 ton 2) key = A[j] 3) //insert A[j] into the sorted sequence All..j-1] 4) left = 1 5) right = j-1 6) while right > left 7) mid = floor((left + right)/2) 8) if key > A[mid] 9) left = mid + 1 10) else right = mid 11) if key > A[left] 12) left = left + 1 13) for i = j downto left + 1 14) A[i] = A[i-1] 15) A[left] key 1) What is the worst case input? What is the best case input? 2) What is the total number of times line 6 is done for the best case and worst case, respectively (with the for loop being taken into account)? Explain your work in sufficient detail. Give the worst case runtime for this line in big-o notation and best case runtime in big-Omega notation. (You may find the formula (3.19) in text page 58 useful: Ig(n!) = O(nlgn). However, it does not mean you have to use the formula to solve this problem.) 3) What is the total number of times line 11 is done for the best case and worst case, respectively (with the for loop being taken into account)? Explain your work in sufficient detail. Give the worst case runtime for this line in big-o notation and best case runtime in big-Omega notation. 4) What is the total number of times line 13 is done for the best case and worst case, respectively (with the for loop being taken into account)? Explain your work in sufficient detail. Give the worst case runtime for this line in big-o notation and best case runtime in big-Omega notation