- Computer Science Engineering (CSE)
- Design and Analysis of Algorithms
- Under what case of Master’s theorem will...

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

A. | 1 |

B. | 2 |

C. | 3 |

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

Answer» B. 2 | |

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

View all MCQs in:
Design and Analysis of Algorithms

- Under what case of Master’s theorem will the recurrence relation of stooge sort fall?
- Under what case of Master’s theorem will the recurrence relation of binary search 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?
- What will be the recurrence relation of the code of recursive selection sort?
- The optimal time obtained through divide and conquer approach using merge sort is the best case efficiency.
- We can solve any recurrence by using Master’s theorem.
- Quick sort uses join operation rather than merge operation.
- Recursive selection sort is a comparison based sort.

Login to Continue

It will take less than 2 minutes

Report MCQ