GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
350 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)   | 350 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 (47.6k points)  
edited by
+1 vote

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 (3k points)  


Top Users Jul 2017
  1. Bikram

    4910 Points

  2. manu00x

    2940 Points

  3. Debashish Deka

    1870 Points

  4. joshi_nitish

    1776 Points

  5. Arjun

    1506 Points

  6. Hemant Parihar

    1306 Points

  7. Shubhanshu

    1128 Points

  8. pawan kumarln

    1124 Points

  9. Arnab Bhadra

    1114 Points

  10. Ahwan

    956 Points


24,099 questions
31,074 answers
70,703 comments
29,407 users