retagged by
1,472 views
10 votes
10 votes
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) n$\log 9/10(n)$

d) 2nlog(n)
retagged by

3 Answers

Best answer
6 votes
6 votes

$T(n) \leq T(\frac{9n}{10})+c$

Only one of the branch will be taken during comparison of A[M] with X.

$TC= O(log_{\frac{10}{9}}n)$

selected by
0 votes
0 votes

It should be logn because in worst case the recurrence relation will be 

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

and we use master theorem to solve this relation then 

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

where a = 1, b = 10/9, 

So nlogb= n log10/9

               = n0

               = 1

and f(n) = 1

so this holds the second case where,

if f(n) =  nlogba logkn then T(n) = nlogbalogn

so in this case k = 0 , hence our solution is T(n) = logn

Answer:

Related questions

0 votes
0 votes
1 answer
1
Sabir Khan asked Aug 8, 2018
1,057 views
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is(A) (n)(B) (logn)(C) (log*n)(D) (1)
4 votes
4 votes
1 answer
2
Aghori asked Nov 5, 2017
1,165 views
There are two sorted list each of length $n$. An element to be searched in the both the lists. The lists are mutually exclusive. The maximum number of comparisons require...
5 votes
5 votes
4 answers
3
Raushank2 asked Jun 28, 2017
2,636 views
I/p - Sorted array of n elementO/p- find any two elements a and b such that (a+b)>1000if lenear search is possible then go to Binary Search and Find time complexity ..?
11 votes
11 votes
2 answers
4
Shubhanshu asked Jun 5, 2017
11,047 views
The average successful search time taken by binary search on a sorted array of $10$ items?$2.6$$2.7$$2.8$$2.9$Answer is $2.9$My doubt:- But when I am using $log_2n$ for $...