Master Theorem Multiple Choice Questions and Answers

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Master Theorem”.

1. Master’s theorem is used for?
a) solving recurrences
b) solving iterative relations
c) analysing loops
d) calculating the time complexity of any code

Explanation: Master’s theorem is a direct method for solving recurrences. We can solve any recurrence that falls under any one of the three cases of master’s theorem.

2. How many cases are there under Master’s theorem?
a) 2
b) 3
c) 4
d) 5

Explanation: There are primarily 3 cases under master’s theorem. We can solve any recurrence that falls under any one of these three cases.

3. What is the result of the recurrences which fall under first case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc?
a) T(n) = O(n^logba)
b) T(n) = O(nc log n)
c) T(n) = O(f(n))
d) T(n) = O(n2)

Explanation: In first case of master’s theorem the necessary condition is that c < logba. If this condition is true then T(n) = O(n^logba).

4. 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) T(n) = O(nlogba)
b) T(n) = O(nc log n)
c) T(n) = O(f(n))
d) T(n) = O(n2)

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)

5. 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)=nc?
a) T(n) = O(nlogba)
b) T(n) = O(nc log n)
c) T(n) = O(f(n))
d) T(n) = O(n2)

Explanation: 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)).
Note: Join free Sanfoundry classes at Telegram or Youtube

6. We can solve any recurrence by using Master’s theorem.
a) true
b) false

Explanation: No we cannot solve all the recurrences by only using master’s theorem. We can solve only those which fall under the three cases prescribed in the theorem.

7. Under what case of Master’s theorem will the recurrence relation of merge sort fall?
a) 1
b) 2
c) 3
d) It cannot be solved using master’s theorem

Explanation: The recurrence relation of merge sort is given by T(n) = 2T(n/2) + O(n). So we can observe that c = Logba so it will fall under case 2 of master’s theorem.

8. Under what case of Master’s theorem will the recurrence relation of stooge sort fall?
a) 1
b) 2
c) 3
d) It cannot be solved using master’s theorem

Explanation: The recurrence relation of stooge sort is given as T(n) = 3T(2/3n) + O(1). It is found too be equal to O(n2.7) using master’s theorem first case.

9. Which case of master’s theorem can be extended further?
a) 1
b) 2
c) 3
d) No case can be extended

Explanation: The second case of master’s theorem can be extended for a case where f(n) = nc (log n)k and the resulting recurrence becomes T(n)= O(nc (log n))k+1.

10. 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)=nc(log n)k?
a) T(n) = O(nlogba)
b) T(n) = O(nc log n)
c) T(n)= O(nc (log n)k+1
d) T(n) = O(n2)

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(nc(log n))k+1.

11. Under what case of Master’s theorem will the recurrence relation of binary search fall?
a) 1
b) 2
c) 3
d) It cannot be solved using master’s theorem

Explanation: The recurrence relation of binary search is given by T(n) = T(n/2) + O(1). So we can observe that c = Logba so it will fall under case 2 of master’s theorem.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]