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

M

Mr. Dubey

🎓 Coach ⭐ 103.11K Points

📊 Design and Analysis of Algorithms

Q. 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)=nc?

(A) none of the below
(B) t(n) = o(nc log n)
(C) t(n) = o(f(n))
(D) t(n) = o(n2)

💬 Discuss

✅ Correct Answer: (B) t(n) = o(nc log n)

Explanation: in 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)

Explanation by: Mr. Dubey

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

💬 Discussion

📊 Question Analytics

👁️

683

Total Visits

📽️

3 y ago

Published

🎖️

Mr. Dubey

Publisher

📈

87%

Success Rate