McqMate

Q. |
## 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? |

A. | none of the below |

B. | t(n) = o(nc log n) |

C. | t(n)= o(nc (log n)k+1 |

D. | t(n) = o(n2) |

Answer» C. t(n)= o(nc (log n)k+1 | |

Explanation: in the extended second case of master’s theorem the necessary condition is that c = logba. if this condition is true then t(n)= o(nc(log n))k+1. |

4.1k

0

Do you find this helpful?

32

View all MCQs in

Design and Analysis of AlgorithmsNo comments yet

- 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?
- 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?
- Under what case of Master’s theorem will the recurrence relation of binary search fall?
- Which case of master’s theorem can be extended further?
- We can solve any recurrence by using Master’s theorem.
- Recurrence equation formed for the tower of hanoi problem is given by
- Which of the following recurrence relations can be used to find the nth fibonacci number?
- What will be the recurrence relation of the code of recursive selection sort?