Question

Estimate how many searches will be needed to justify time spent on presorting an array of 101 elements if sorting is done by mergesort and searching is done by binary search. You may assume that all searches are for elements known to be in the array. What about an array of 105 elements?

Answer 1

Answer:

Merge sort is sort, which contains the same elements in the array to maintain original positions concerning each other. Complexity of sort is O (nLogn) and runtime is O(nlogn)

Explanation:

Estimate time spent on presorting an array 101 element in merge and binary search, two schemes can be used in the first scheme if 101 items in sequential search then use the complexity of O(n). In the second scheme covert, the list into an array then sort an array with the complexity of O(n log n) and fetch the 101 elements.

Merge 101 elements; presorted sub-array n items have to compare the top times in sub-array and choose the maximum item and place it in a sorted array. Time for merging is proportional to ( k-1) n.

Suppose the processing time of the merger is c.(k-1) .n then scale factor has the same value.

The processing time of a sorting array is a recurrence equation.

T(n) = 3T (n/3) + 2 cn

Similarly this implement for array of 105 element.