Consider the following pseudocode. Algorithm multisearch( data, target ): data a
ID: 3912944 • Letter: C
Question
Consider the following pseudocode. Algorithm multisearch( data, target ): data an list of arrays of integers; in each array the integers are sorted in ascending order; the list ' data has a cursor target: an integer // Iterate over the arrays in the list 'data' using // its cursor: data.goFirstO found false while !data. after and !found // search for integer 'target' in A found binarySearch (data. currentItem), target) data.goForth) Using the active operation approach to timing analysis determine the time complexity of this pseu- docode in the worst case. Assume that the list of arrays contains n arrays and that each array has exactly m items in it. Show all your work and express your final answer in Big-O notation.Explanation / Answer
Given a List of Arrays, where number of arrays in the list is n and size of each array is m.
According to pseudocode, To search a target element in a list,
there is need to iterate over each array in the list followed by a binary search in each array for given target element.
First,check complexity of Binary search:-
Binary search(A[],low,high,Target)
while(low<high)
mid=(low+high)/2
if(A[mid]==target)found at index mid;
else if(A[mid]<target)
low=mid+1;
else if(A[mid]>target)
high=mid-1;
Recursive equation for Binary search T(m)=T(m/2)+O(1)
Time complexity of binary search=O(log m)if size of array is m.
According to Question,
In worst case,target element will found in last Array of the list,Hence there is need to iterate over all array in list i.e. iterating loop will run for n time,followed by a binary search with complexity O(log(m)),where m is size of array.
Therefore ,overall complexity of multiplesearch is
O(nlogm)