GATE CSE 1994 | Question: 1.7, ISRO2017-14

Question

The recurrence relation that arises in relation with the complexity of binary search is:

• A. $T(n) = 2T\left(\frac{n}{2}\right)+k, \text{ k is a constant }$

• B. $T(n) = T\left(\frac{n}{2}\right)+k, \text{ k is a constant }$

• C. $T(n) = T\left(\frac{n}{2}\right)+\log n$

• D. $T(n) = T\left(\frac{n}{2}\right)+n$

Answer 1

Its Option B.

Because, in binary search we reduce the search space into half at each comparison.

For more information check out link below... just to get an idea on how binary search works

https://www.flowerbrackets.com/binary-search-java/

Hope it helps!!!

Answer 2

Since, with every iteration of binary search, data set to be searched is divided into half of the original data set.Also,some constant time is lapsed during iteration during each iteration.So, recurrence relation for Binary search would be:

T(n)  =   T(n/2)   +   k,   where k is a constant.

Answer 3

They are asking about Binary search that is when array is already sorted with distinct element we can directly jump to middle and after comparing middle we can either go peft or go right we have to follow one path..

Ie T(n2) + k