1. Computer Science Engineering (CSE)
  2. Design and Analysis of Algorithms
  3. What is the result of the recurrences wh...
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.

Discussion