McqMate

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

1.2k

0

Do you find this helpful?

10

View all MCQs in

Design and Analysis of AlgorithmsNo comments yet

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