Question

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)=n^c(log n)k?

(a) T(n) = O(nlogba)

(b) T(n) = O(n^c log n)

(c) T(n)= O(n^c (log n)^k+1

(d) T(n) = O(n^2)

This question was posed to me in homework.

This is a very interesting question from Masters theorem topic in division Recursion of Data Structures & Algorithms II

Answer 1

Right option is (c) T(n)= O(n^c (log n)^k+1

The best 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(n^c(log n))^k+1.