in Algorithms retagged by
2,210 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?
in Algorithms retagged by
by
2.2k views

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.)

2 Comments

@Bongbirdie mam
Please describe A1 in more detail :D

0
0
In divide and conquer 3/2 n -2

In  sequential search

n-1
0
0
1 vote
1 vote
I think both will be equal as in both cases order(2×n) time will be taken

Related questions