Suppose the first step in binary search algorithm is changed to M = (9L+R)/10, we know that the complexity of binary search is log(n). What will be the complexity of modified search?

a) log(n)

b) n

c) nlog9/10(n)

d) 2nlog(n)

# Modified binary search time complexity,very conceptual

**supriyas**#1

**geetam**#2

lets take L =1 and R = 1000,

then first element which will be compared = 9L+R/10 = 9 + 1000/10 = 100

so either a100 will be equal to the value we are searching or we continue searching 9/10 part in worst case,

so in 1 one iteration we are eliminating 1/10 of array,

b opts out,those who thinks they are thinking array of 10 elements.Thing big.

nlog(n) nopes cant be greater than n.

so lets see a or c,i will mark a

log(9/10) 10000 if n = 10000 ,will be

(9/10)^k = 1000.

k (log 9 - log 10) = 3

k will be negative so i think c is also not.

LIke in normal binary search, we divide array in 2 parts n/2

Suppose a worst case, we have to iterate the array k times

n/2^k =1 or n= 2^k or k= log n

But in this case supposing 11 elements,

0-10 9*0+10/10 =1, mid=1
1-10 9*1+10/2, mid= 9

1-9 9*1+9/2 = 8, just not to repeat the case

1-8 9+8/2 = 7

Answer seems to be O(n)

Dont think for small values for n =10 ,it gives O(n),but as geetam said think big,when you think of 1000 elements,you realise we are elimanating 1/10 of array by one comparision,

so if arrray has 10 lakh values ,we are eliminating 1 lakh in first comparision,then 9 lakh in secind comaprison,then 8.1 lakhs in third comparision in worst case, so its not 0(n) obviously

I think it’s logn.

it works same as the partitioning in quicksort hence, other than the worst case i.e, n-1 and 1 will get the best case available.

& one-tenth is not the worst case.

So it’ll not change.

**Ruturaj**#6

It’s quite simple. At each step of the algorithm we are dividing the array in the ratio 1:9.

So the recurrence relation would be,

T(n)= T(n/10) + T(9n/10) + 1

Here the term T(9n/10) will be significant in determining the worst case of the algorithm.

Solving the above recurrence relation we would get the answer as

T(n)= log<base 10/9> n

So option (a) is correct.

**Abbas**#7

Any algo that divides the iterarion in a certain constant base partition, eg. 1:1,2:4, 8,10, 2:20000, or as given 9:1

The complexity remains Log N only,

Only the base of log changes.