The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
4.6k 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$

asked in Algorithms by Veteran (52.1k points) | 4.6k views

7 Answers

+28 votes
Best answer

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

answered by Boss (19.9k points)
edited by
+10 votes

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

http://www.geeksforgeeks.org/binary-search/

answered by
+9 votes
answer is B in binary search once checked with middle value. we need to do the operation only with one half of the array.
answered by Boss (11.1k 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
+9 votes

option B is correct...

answered by Boss (40.9k 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
any issues Shraddha???
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

@shraddha_gami 

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

And answer is Option A

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.
+5 votes

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

http://www.flowerbrackets.com/binary-search-program-java/

Hope it helps!!!

answered by (61 points)
–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
answered by Active (4k points)
–2 votes
Option B
answered by Active (2.8k points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,807 questions
54,504 answers
188,309 comments
74,884 users