GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
256 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)   | 256 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

+3 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 (40.8k 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 Jan 2017
  1. Debashish Deka

    8968 Points

  2. sudsho

    5326 Points

  3. Habibkhan

    4798 Points

  4. Bikram

    4532 Points

  5. Vijay Thakur

    4486 Points

  6. saurabh rai

    4222 Points

  7. Arjun

    4196 Points

  8. santhoshdevulapally

    3808 Points

  9. Sushant Gokhale

    3596 Points

  10. Kapil

    3486 Points

Monthly Topper: Rs. 500 gift card

19,212 questions
24,104 answers
53,150 comments
20,319 users