recategorized by
17,935 views
29 votes
29 votes

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$

recategorized by

7 Answers

Best answer
44 votes
44 votes

Correct Option: B

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

edited by
15 votes
15 votes

option B is correct...

11 votes
11 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.
Answer:

Related questions

35 votes
35 votes
6 answers
1
Kathleen asked Oct 4, 2014
13,786 views
Let $A$ and $B$ be any two arbitrary events, then, which one of the following is TRUE?$P (A \cap B) = P(A)P(B)$$P (A \cup B) = P(A)+P(B)$$P (A \mid B) = P(A \cap B)P(B)$$...
21 votes
21 votes
7 answers
2
Kathleen asked Oct 4, 2014
18,308 views
Algorithm design technique used in quicksort algorithm is?Dynamic programmingBacktrackingDivide and conquerGreedy method
15 votes
15 votes
7 answers
3
Kathleen asked Sep 18, 2014
11,672 views
The problem $\text{3-SAT}$ and $\text{2-SAT}$ are both in $\text{P}$both $\text{NP}$ complete$\text{NP}$-complete and in $\text{P}$ respectivelyundecidable and $\text{NP}...
33 votes
33 votes
4 answers
4
Kathleen asked Oct 5, 2014
8,847 views
An instance of a relational scheme $R(A, B, C)$ has distinct values for attribute $A$. Can you conclude that $A$ is a candidate key for $R?$