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
View Answer
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
View Answer
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)
View Answer
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)
View Answer
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)
View Answer
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)).
6. We can solve any recurrence by using Master’s theorem.
a) true
b) false
View Answer
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
View Answer
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
View Answer
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
View Answer
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)
View Answer
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
View Answer
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.
- Apply for Computer Science Internship
- Check Programming Books
- Practice Data Structure MCQ
- Practice Computer Science MCQs
- Practice Programming MCQs
