Question

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

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

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

(c) T(n) = O(f(n))

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

This question was addressed to me in an interview.

This question is from Masters theorem topic in section Recursion of Data Structures & Algorithms II

Answer 1

Right option is (c) T(n) = O(f(n))

The best I can explain: In third case of master’s theorem the necessary condition is that c > logba. If this condition is true then T(n) = O(f(n)).