The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+5 votes
400 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 (371 points) | 400 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

+5 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 (50.8k 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 (3.2k points)

Related questions

0 votes
1 answer
2
0 votes
0 answers
3
asked ago in Algorithms by saxena0612 Boss (5k points) | 35 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,156 questions
36,980 answers
92,147 comments
34,822 users