# Master Theorem Multiple Choice Questions and Answers (MCQs) – 2

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)

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

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)

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

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

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

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

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

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)

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)

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)

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]