This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Master Theorem – 2”.
1. Solve the following recurrence using Master’s theorem.
T(n) = 4T (n/2) + n2
a) T(n) = O(n)
b) T(n) = O(log n)
c) T(n) = O(n2log n)
d) T(n) = O(n2)
View Answer
Explanation: The given recurrence can be solved by using the second case of Master’s theorem.
T(n) = O(nc log n) = Here nc = n2
So the solution becomes T(n) = O(n2log n).
2. Solve the following recurrence using Master’s theorem.
T(n) = T (n/2) + 2n
a) T(n) = O(n2)
b) T(n) = O(n2 log n)
c) T(n) = O(2n)
d) cannot be solved
View Answer
Explanation: The given recurrence can be solved by using the third case (as f(n) > log21) of Master’s theorem.
T(n) = O(f(n)) = Here f(n) = 2n.
So the solution becomes T(n) = O(2n).
3. Solve the following recurrence using Master’s theorem.
T(n) = 16T (n/4) + n
a) T(n) = O(n)
b) T(n) = O(log n)
c) T(n) = O(n2log n)
d) T(n) = O(n2)
View Answer
Explanation: The given recurrence can be solved by using the first case of Master’s theorem. So the solution becomes T(n) = O(n2).
4. Solve the following recurrence using Master’s theorem.
T(n) = 2T (n/2) + n/ log n
a) T(n) = O(n)
b) T(n) = O(log n)
c) T(n) = O(n2log n)
d) cannot be solved using master’s theorem
View Answer
Explanation: The given recurrence cannot be solved by using the Master’s theorem. It is because this recurrence relation does not fit into any case of Master’s theorem.
5. Solve the following recurrence using Master’s theorem.
T(n) = 0.7 T (n/2) + 1/n
a) T(n) = O(n)
b) T(n) = O(log n)
c) T(n) = O(n2log n)
d) cannot be solved using master’s theorem
View Answer
Explanation: The given recurrence cannot be solved by using the Master’s theorem. It is because in this recurrence relation a < 1 so master’s theorem cannot be applied.
6. Solve the following recurrence using Master’s theorem.
T(n) = 4 T (n/2) + n!
a) T(n) = O(n!)
b) T(n) = O(n! log n)
c) T(n) = O(n2log n)
d) cannot be solved using master’s theorem
View Answer
Explanation: The given recurrence can be solved by using the third case of Master’s theorem. So the solution becomes T(n) = O(n!).
7. Solve the following recurrence using Master’s theorem.
T(n) = 4T (n/4) + n log n
a) T(n) = O(n (log n)2)
b) T(n) = O(n log n)
c) T(n) = O(n2log n)
d) cannot be solved using master’s theorem
View Answer
Explanation: The given recurrence can be solved by using the extended second case of Master’s theorem. So the solution becomes T(n) = O(n (log n)2).
8. What will be the recurrence relation of the following code?
Int sum(int n) { If(n==1) return 1; else return n+sum(n-1); }
a) T(n) = T(n/2) + n
b) T(n) = T(n-1) + n
c) T(n) = T(n-1) + O(1)
d) T(n) = T(n/2) + O(1)
View Answer
Explanation: As after every recursive call the integer up to which the sum is to be calculated decreases by 1. So the recurrence relation for the given code will be T(n) = T(n-1) + O(1).
9. What will be the recurrence relation of the following code?
int xpowy(int x, int n) if (n==0) return 1; if (n==1) return x; if ((n % 2) == 0) return xpowy(x*x, n/2); else return xpowy(x*x, n/2) * x;
a) T(n) = T(n/2) + n
b) T(n) = T(n-1) + n
c) T(n) = T(n-1) + O(1)
d) T(n) = T(n/2) + O(1)
View Answer
Explanation: As after every recursive call the integer up to which the power is to be calculated decreases by half. So the recurrence relation for the given code will be T(n) = T(n/2) + O(1). It can be solved by using master’s theorem.
10. What will be the time complexity of the following code?
int xpowy(int x, int n) { if (n==0) return 1; if (n==1) return x; if ((n % 2) == 0) return xpowy(x*x, n/2); else return xpowy(x*x, n/2) * x; }
a) O(log n)
b) O(n)
c) O(n log n)
d) O(n2)
View Answer
Explanation: As the recurrence relation of the code is given by T(n) = T(n/2) + O(1) so it can be solved by using master’s theorem second case.
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]
- Practice Programming MCQs
- Check Design and Analysis of Algorithms Books
- Check Programming Books
- Practice Data Structure MCQ
- Apply for Computer Science Internship
