In the INSERTION-SORT algorithm in Sec. 2.1 line 5-7 uses a linear search through the sorted subarray A[1..j =1] to find the proper position for A[J]. The following is a variant of Insertion Sort where linear search is modified into (iterative) binary search (given A [1..j-1] is a sorted sub-sequence). Can the overall running time of this version of the insertion sort be improved to Theta(nlgn)? Answer the questions below- B Insertion Sort (A, n) for j leftarrow 2 to a key leftarrow = A[j]//insert A[j] into the sorted sequence A[1.. j-1] left leftarrow 1 right leftarrow- j-1 while left) mid leftarrow floor (left + right)/2) if key > A[mid] left leftarrow mid +1 else right leftarrow mid if key > A[left] left leftarrow left +1 for i leftarrow- j downto left +1 A[i] leftarrow- A[i-1] A[left] leftarrow- key Describe what make the worst case and the best case (the input characteristics, not the runtime), respectively. Write down the number of times that line 11, 12, 13, and 14 are executed in the worst Case Write down the number of times that line 11, 12, 13, and 14 are executed in the best Case Comparison operation at line 8 is the key operation in the binary search process (the while loop). The total number of comparisons is the factor that determines the order of growth for the binary search process. Give the total number of comparisons (at line 8) in the worst case in big-Theta notation. Explain your answer in detail. Give the total number of comparisons (at line 8) in the best case in big-Theta notation. Explain your answer in detail. Give the worst-case running time in big-o notation. Show your work. Give the best-case running time in big-Omega notation. Show your work. When the given array A is sorted, is it good to apply this version of Insertion Sort, as oppose to the vanilla version? Explain