I need a detailed line-by-line analysis of binary insertion sort in the style of the example insertsort. Looking for how many times each line happens (for example the out for loop happens N times) and a combining of all the steps into a big O analysis.

Binary InsertionSort (A, n) 1) for j = 2 to n 2) key = A[j] 3) //insert A[j] into the sorted sequence A[1..j-1] 4) left = 1 5) right = 3-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 cost times = C1 n C2 n 1 0 n 1 INSERTION-SORT(A) 1 for j 2 to A.length 2 key = A[j] 3 // Insert A[j] into the sorted sequence A[1.. j - 1]. 4 i = j - 1 5 while i > 0 and A[i] > key 6 A[i + 1] = A[i] 7 i = i - 1 8 A[i + 1] = key C4 n - 1 C5 C6 {j=2t; =2(t; 1) =2(t; 1) n C7 C8 n - 1