Question

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)=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)

I got this question by my college professor while I was bunking the class.

Question is taken from Masters theorem topic in chapter Recursion of Data Structures & Algorithms II

Answer 1

The correct choice is (b) T(n) = O(n^c log n)

To explain: In 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)