1,384 views
6 votes
6 votes

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?

2 Answers

Best answer
7 votes
7 votes

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 

edited by
1 votes
1 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

Related questions