GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
318 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)   | 318 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.2k 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 May 2017
  1. akash.dinkar12

    3302 Points

  2. pawan kumarln

    1776 Points

  3. Bikram

    1646 Points

  4. sh!va

    1640 Points

  5. Arjun

    1396 Points

  6. Devshree Dubey

    1272 Points

  7. Debashish Deka

    1142 Points

  8. Angkit

    1044 Points

  9. LeenSharma

    1000 Points

  10. Arunav Khare

    754 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    732 Points

  2. Arnab Bhadra

    402 Points

  3. pawan kumarln

    402 Points

  4. bharti

    304 Points

  5. LeenSharma

    238 Points


22,823 questions
29,142 answers
65,209 comments
27,666 users