GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
292 views

Consider the following exponential search algorithm(ES). The array of n elements have to be searched is divided in to logn parts. The ith part is from index 2^{i-1} to2^{i}. to search an element search all the parts one by one from left to right using binary search algorithm. What is the worst case complexity of above searching algorithm?

 

 

asked in Programming by (357 points)   | 292 views
I have assumed that every part is sorted  and the whole  array is unsorted

In the question it is written that binary search is applied to every part. So if we are applying binary search then we should assume that every part should be sorted otherwise there is no point of using binary search.

List 1 1 elements

List 2  2 elements

List 3 4 elements

List 4 8 elements

list logn  2^(log(n) - 1 )

worst case occurs when element is not present in the array so

if we apply binary search in each part then

total time complexity= log(1)+log(2) +log(4).......log(2^log(n) -1)

     =log(1.2.4.....2^log(n)-1)  

     =O(log(n)*log(n))
elements are not sorted.if you do binary search unsorted array it will take o(n) time at worst case why you are taking log n time plz xplain
@SayanDas1 Where in the problem statement is it mentioned that the array is unsorted?
They are looking for worst case complexity so i assume that it will be unsorted
Binary search doesn't work on unsorted arrays.Worst case of binary search is always based on its prerequisite condition of a sorted array.

If you try to apply binary search on an unsorted array then this  question doesn't make sense.

2 Answers

+4 votes
Best answer

As Binary search algorithm is applied in each part, we have to take each array part sorted .

Total N elements are divided into Log N parts .

Each part contains elements in power of 2, and parts are like,

( 1 element ) ( 2 elements ) ( 4 elements ) ( 8 elements ) ( 16 elements ) ..........( 2log2n - 1 elements ).

Hence, applying binary search algorithm in each of the parts starting from left to right,

Log (1) + Log (2) + Log (4) + Log (8) + log (16) + ................ + Log (2log2n - 1 )

Log ( 1.2.4.8.16........(2log2n - 1) )

Log ( 2. 21 . 2. 2. 2............. (2log2n - 1 ) ) 

Log ( 2 (1 + 2 + 3 + 4 +............ +log2n - 1 ) 

O(Log ( 2 (log2n - 1). (log2n) / 2 )) ==> O((Logn - 1)(Logn ) / 2) ==> O(Log2 n)2 

 

 

answered by Veteran (44.9k points)  
edited by
0 votes

The worst time complextiy for an binary search will be, when it search in the biggest set of part which is (2i-1 to 2i). As the number distribution is not equal, last set of array have the maximum set of number. for doing this we required to have log2(n) comperison.

so can we say that worst time for this algorithm to search is.

T(n) = T((2log2n-1 - 2log2n))/2 + log2n

answered by Loyal (2.7k points)  


Top Users Mar 2017
  1. rude

    4018 Points

  2. sh!va

    2994 Points

  3. Rahul Jain25

    2804 Points

  4. Kapil

    2608 Points

  5. Debashish Deka

    2104 Points

  6. 2018

    1414 Points

  7. Vignesh Sekar

    1336 Points

  8. Bikram

    1218 Points

  9. Akriti sood

    1186 Points

  10. Sanjay Sharma

    1016 Points

Monthly Topper: Rs. 500 gift card

21,446 questions
26,759 answers
60,943 comments
22,955 users