Assume you are given a sorted array A of n numbers, where A is indexed from 1 up
ID: 3747630 • Letter: A
Question
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.
Explanation / Answer
Algorithm for Sequential search in sorted array
Function :search
Arguments: list of n elements and a search element
Returns: Position where it is found
Begin
For index i from 0 to n(end of an array)
If list[index i]==search element then
Return index;
End if
End For loop
End
Here single for loop is enough to search and find the position of a search element in an array.
In worst case ie either search element is found at the end of the list or it is not found then n comparisons are performed.
Inside Loop
1)Each time index i is compared to n to check whether index is within the boundary of array(ie)
i<=n - 1 operation
2)Then list[i] is compared with search element
If(list[i]==search element) - 2 operations( list[i], ==)
3)i is incremented as i++ - 1 operation
Apart from that there is one initialization(i=0) and one return statement(return index).
So 4 operations inside the loop and 2 one time operations are performed
So
T(n)=4n+2
(ie) 4 operations are performed repeatedly for n times in worst case scenario.
Thus T(n)=O(n).
Algorithm for Moving elements in a sorted array
Function :MakeRoom
Arguments: list of n elements and a position
Returns: Move elements one position to the right from position index
Begin
For index p to n(end of an array)
Move elements one position right from nth element to position p th element
End if
End For loop
End
Here single for loop is enough to move all elements (from p to n)to one position right.
In worst case ie if the first element is the pth element then n movements are performed.
Inside loop
1)Each time index p is compared to n to check whether position is within the boundary of array(ie)
p<=n - 1 operation
2) if p=1 ,then n movement are performed arr[i]=arr[i-1]-> 2 operation(n times)
2)i is incremented as i++ - 1 operation
So 3 operations inside the loop and 1 one time operations are performed
So
T(n)=3n+1
(ie) 3 operations are performed repeatedly for n times in worst case scenario(if p=1).
Thus T(n)=O(n).
Algorithm for Insert an elements in a sorted array at particular position
Function :Insert
Arguments: list of n elements,new element
Returns : New element is inserted at P position
Begin
Calls search function to search an element
Function :search
Arguments: list of n elements, search element
Returns: index Position where search element is found
Calls MakeRoom function to move elements of an array
Function :MakeRoom
Arguments: list of n elements, position of search element
Returns: Move elements one position right from nth element to position p th element
List [position]= new element
End
If searching element is found in a first place(best case) then MakeRoom will need to perform n movements (worst case) .If search element is found at the last position(worst case) then MakeRoom will need to perform only 1 movement (best case).
One worst case will make another function as best case.
(ie) T(n)=O(n)+O(1) (or) O(1)+O(n)=O(n)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.