Consider the recurrence function T(n) = 32T(n/2) + 5n^3 log n In giving an expre
ID: 3576645 • Letter: C
Question
Consider the recurrence function T(n) = 32T(n/2) + 5n^3 log n In giving an expression for the runtime T(n) if the recurrence can be solved with the Master Theorem. Assume that T(n) = 1 for n lessthanorequalto 1, which of the following is true? Select one: a. Master Theorem Case 1 holds and the overhead is growing faster than the sub-problems. b. Master Theorem Case 2 holds and the sub-problems are growing at the same rate as the overhead. c. Master Theorem Case 1 holds and the sub-problems are growing faster than the overhead. d. Master Theorem Case 3 holds and sub-problems are growing at a slower rate than the overhead. e. Master Theorem Case 2 holds and the overhead are growing faster than the sub-problems.Explanation / Answer
In given recursive expression a=32,b=2
f(n)=5n3logn from then case 2 holds c=logba ,c=5
so k=1 solution T(n)=nlogbalogk+1n
T(n)=(n5logn),
f(n)=consider as overhead
e)Master Theorem case 2 holds and the overhead are growing faster than the subproblems