McqMate

Q. |
## Under what case of Master’s theorem will the recurrence relation of binary search fall? |

A. | 1 |

B. | 2 |

C. | 3 |

D. | it cannot be solved using master’s theorem |

Answer» B. 2 | |

Explanation: the recurrence relation of binary search is given by t(n) = t(n/2) + o(1). so we can observe that c = logba so it will fall under case 2 of master’s theorem. |

2.5k

0

Do you find this helpful?

19

View all MCQs in

Design and Analysis of AlgorithmsNo comments yet

- Under what case of Master’s theorem will the recurrence relation of merge sort fall?
- Under what case of Master’s theorem will the recurrence relation of stooge sort fall?
- What is the result of the recurrences which fall under second case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc?
- What is the result of the recurrences which fall under third case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc?
- What is the result of the recurrences which fall under the extended second case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc(log n)k?
- We can solve any recurrence by using Master’s theorem.
- What will be the recurrence relation of the code of recursive selection sort?
- Which theorem gives the relation between the minimum vertex cover and maximum matching?
- What is the time complexity of the above recursive implementation of binary search?
- Can binary search be applied on a sorted linked list in O(Logn) time?