1. Perform the execution of the following pseudocode with the array A= [8,0,2,1,9,3] INSERTION-SORT(A) 1 for...

 

Transcribed Image Text:

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[A] do key A[j] 12345678 Insert A[j] into the sorted sequence A[1.. j - 1]. i- j-1 while i 0 and A[i]> key do A[i+1] A[i] i-i-1 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? 3. For a given iteration of the loop for, can we know exactly the number of iterations of the loop while (line 5) ? 4. In general, consider any loop: what is the relation between the number of execution of the loop header and that loop 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? 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[A] do key A[j] 12345678 Insert A[j] into the sorted sequence A[1.. j - 1]. i- j-1 while i 0 and A[i]> key do A[i+1] A[i] i-i-1 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? 3. For a given iteration of the loop for, can we know exactly the number of iterations of the loop while (line 5) ? 4. In general, consider any loop: what is the relation between the number of execution of the loop header and that loop 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?