in Algorithms
2,039 views
1 vote
1 vote
There are two sorted list each of length n. An element to be searched in the both the lists. The lists are mutually exclusive. The maximum number of comparisons required using binary search and find its time complexity?
in Algorithms
2.0k views

4 Comments

If element is not in both list then
0
0
The complexity will be 2×logn which is equivalent to simply O(logn). We could just apply binary search on both the arrays.
0
0
O(2n) + O(log 2n)=O(n)?
0
0

4 Answers

1 vote
1 vote
Since  both the array are sorted, then we can apply the BINARY SEARCH

 Array 1

 Array 2

 Suppose searching element=X

 First apply the BINARY search in array 1, if element found  then well and good

TC will be ○(logn)

 But

If element not found in array 1,then appy the BINARY search in array  2,again in will take logn time ,but

Now,overall  time must be 2logn but asymtotically  the  TC WILL BE = ○(logn)
0 votes
0 votes
Since both the Lists are sorted and mutually exclusive, so we can consider Binary search for which time complexity is O( log n).
0 votes
0 votes

The recurrence relation for binary search is 

 T(n) = T(n/2) + 2,  T(1) = 1

and the no. of comparsions is 2Log2n + 1 this is for one list

for 2 list => 2*(2Log2n + 1)

and the time complexity is O(logn) 

0 votes
0 votes
time complexity for doing binary seach on first list  = log n

time complexity for doing binary search on second list = log n

total = 2log n = O(log n )

Related questions