Modified binary search time complexity,very conceptual


#1

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)


#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.


#3

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 90+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)


#4

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


#5

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.


#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.


#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.