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

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)=n^{c}?

a) T(n) = O(n^log_{b}a)

b) T(n) = O(n^{c} log n)

c) T(n) = O(f(n))

d) T(n) = O(n^{2})

View Answer

Explanation: In first case of master’s theorem the necessary condition is that c < log

_{b}a. If this condition is true then T(n) = O(n^log

_{b}a).

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)=n^{c}?

a) T(n) = O(nlog_{b}a)

b) T(n) = O(n^{c} log n)

c) T(n) = O(f(n))

d) T(n) = O(n^{2})

View Answer

Explanation: In second case of master’s theorem the necessary condition is that c = log

_{b}a. If this condition is true then T(n) = O(n

^{c}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)=n^{c}?

b) T(n) = O(nlog_{b}a)

b) T(n) = O(n^{c} log n)

c) T(n) = O(f(n))

d) T(n) = O(n^{2})

View Answer

Explanation: In third case of master’s theorem the necessary condition is that c > log

_{b}a. 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 = Log

_{b}a 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(n

^{2.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) = n

^{c}(log n)

^{k}and the resulting recurrence becomes T(n)= O(n

^{c}(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)=n^{c}(log n)k?

a) T(n) = O(nlog_{b}a)

b) T(n) = O(n^{c} log n)

c) T(n)= O(n^{c} (log n)^{k+1}

d) T(n) = O(n^{2})

View Answer

Explanation: In the extended second case of master’s theorem the necessary condition is that c = log

_{b}a. If this condition is true then T(n)= O(n

^{c}(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 = Log

_{b}a 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__.