4.7k views

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

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

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

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

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

| 4.7k views

It is B. searching for only one half of the list. leading to $T(n/2)$+ constant time in comparing and finding mid element.

by Boss (19.9k points)
edited by

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

http://www.geeksforgeeks.org/binary-search/ by option B is correct...

by Boss (41.8k points)
0
+1

https://gateoverflow.in/2444/gate1994_1-7

i selected option A

and worst case to search in BST is O(n)

Option B is may be for balanced BST

0
0
@akash

worst case for BST is O(n)
+1
I think, u are not reading question carefully. They are asking about Binary Search algorithm which is used in searching of elements in ordered lists..
0

Yeah! i know that

what if tree is ordered and only one sided

like this +2

The question is about binary search not for binary search tree . hope u get the point ??

0

@papesh

Still I didn't get that

It is not always possible that we start search from middle element.

And the concepts are related to each other that's the reason I shown the BST.

It is Gate 1994 question

https://gateoverflow.in/2444/gate1994_1-7

0
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
0
it seems easy by using master theoram.
answer is B in binary search once checked with middle value. we need to do the operation only with one half of the array.
by Boss (11k points)
0
sir, it means we always apply operation in the tree with in-order traversal because in-order is sorted

if elements in the list are 3,7,1,2,9 and they are asking to form a binary tree then we will first sort it in ascending order and then form a tree? but I think we make a tree with 3 as a parent and then right is 7 then left of 3 is 1 like this? A BIG confusion arises

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!!!

by (61 points)
edited by
–1 vote
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
by Active (4.1k points)
Option B
by Active (2.7k points)