please send answer for part b iii please send proper answer 0 and A[j] > K doA[j + 1] + A[j]j+j-1A[j] +3478 return Ai. Write the array A after each iteration of the outer For-loop, and state...

please send answer for part b iii

please send proper answer

Extracted text: 2. (a) Write an algorithm in pseudo-code that • takes as input an array A[1...n], and an item M which occurs at least once in A. • returns the index (position) of the last occurrence of the item M in array A. The following table shows some examples with the expected output of the algorithm (the last occurrences of M is underlined): input: A output [1,8, 1, 7, 1, 9 [4, 3, 2, 2, 2, 3] 2 [9, 9] [3, 3, 3, 3] [4, 3, 3, 3] 1 9. 4 4 Your algorithm should perform as few comparisons as possible. (b) Consider using the following algorithm on an array A = [5,: Input: Array A[1...n] Output: ?? 1 for i + 2 to n do K+ A[i] j+i-1 while j > 0 and A[j] > K do A[j + 1] + A[j] j+j-1 A[j] + 3 4 7 8 return A i. Write the array A after each iteration of the outer For-loop, and state what you think the algorithm does. Show all your working. ii. How many times will line 5 be executed for the array A? How many times for an array of length n? ii. How many times will line 4 be executed in the worst case for the array A? How many times for an array of length n?