Data Structures & Algorithms Multiple Choice Questions on “Master’s 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
Answer: a
Clarification: 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
Answer: b
Clarification: 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)
Answer: a
Clarification: 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)
View Answer
Answer: b
Clarification: 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)
Answer: c
Clarification: 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)).
6. We can solve any recurrence by using Master’s theorem.
a) true
b) false
Answer: b
Clarification: 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
Answer: b
Clarification: 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
Answer: a
Clarification: 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
Answer: b
Clarification: 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)
Answer: c
Clarification: 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
Answer: b
Clarification: 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.