Exercise 1: [ Insertion-Sort] 1. Perform the execution of the following pseudocode with the array A- [8,0,2,1,9,3] INSERTION-SORT (A) 1 for j2 to length[Al 2 3 4 5 6 7 8 do key ALj] Insert A[j] into the sorted sequence A . j-1] while i O and A[i] >key do A [i + 1] A[ A[i + 1] key Loop invariants and the correctness of insertion sort 2. Is the number of executions of the line 5 the same for all the iterations of the for loop? the number of iterations of the loop while (line 5)? the number of execution of the loop header and that loorp 3. For a given iteration of the loop for, can we know exactly 4. In general, consider any loop: what is the relation betweein body. 5. For the pseudocode above, compute the running time T(n) where n is the size of the A 6. What is the best case? what is its running time? 7. What is the worst case? what is its running time