retagged by
2,890 views
4 votes
4 votes
Consider the problem of computing min-max in an unsorted array where min and max are minimum and maximum elements of array. Algorithm A1 can compute min-max in a1 comparisons without divide and conquer. Algorithm A2 can compute min-max in a2 comparisons by scanning the array linearly. What could be the relation between a1 and a2 considering the worst case scenarios?
retagged by

2 Answers

2 votes
2 votes
Algorithm A1 finds the min max without div and conquer means that binary search is not used. So, it is linear search. Time complexity is O(n).

Algorithm A2 scans the entire array linearly. So, this is also performing a linear search in time O(n).

 

Hence, A1=A2.( with respect to time.)
1 votes
1 votes
I think both will be equal as in both cases order(2×n) time will be taken

Related questions

0 votes
0 votes
1 answer
1
Aspi R Osa asked Dec 14, 2015
1,511 views
Consider a set of 20 elements.To find maximum and minimum element in the given set, the minimum number of comparisons required is _________? (using DAC Max-Min algorithm)...
2 votes
2 votes
1 answer
4
srestha asked Dec 22, 2016
803 views
Assume that A be an array of 16 elements. What is the difference between maximum number of inversion and minimum number of inversion for the array with 16 elements?