Assume you are given a sorted array A of n numbers, where A is indexed from 1 up to n, and a number num which we wish to insert into A, in the proper sorted position. The function Search finds the minimum index i such that num should be inserted into A[i]. It searches the array sequentially until it finds the location i. Another function MakeRoom moves A[i], , A[n] to A[i+1]A[n+1].

a) [5 points] Write an algorithm for the function Search, using the same sort of C++- like pseudocode used in the text. Do a worstcase analysis of your algorithm, counting comparisons of num with array elements.

b) [5 points] Write an algorithm for the function MakeRoom, using the same sort of C++-like pseudocode used in the text. Do a worst-case analysis of your algorithm, counting each time an array element is moved. If you use any sort of swap routine, this would count as 2 moves of array elements.

c) [5 points] The algorithm Insert which inserts num into A consists of calling Search and then MakeRoom. Do a worst-case analysis of Insert, counting both comparisons of num with elements in A, and counting whenever an element of A is moved.