[Solved] 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?

McqMate

Q.	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?
A.	none of the below
B.	t(n) = o(nc log n)
C.	t(n) = o(f(n))
D.	t(n) = o(n2)
Answer» B. t(n) = o(nc log n)
Explanation: in 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)

5k

0

Do you find this helpful?

34

View all MCQs in

Design and Analysis of Algorithms

Discussion

No comments yet

Related MCQs

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 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?
We can solve any recurrence by using Master’s theorem.
Recurrence equation formed for the tower of hanoi problem is given by
Which case of master’s theorem can be extended further?
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?