250+ TOP MCQs on Master’s Theorem Multiple Choice Questions and Answers (MCQs) and Answers

Data Structures & Algorithms Multiple Choice Questions on “Master’s Theorem – 2”.

1. Solve the following recurrence using Master’s theorem.
T(n) = 4T (n/2) + n²
a) T(n) = O(n)
b) T(n) = O(log n)
c) T(n) = O(n²log n)
d) T(n) = O(n²)

Answer: c
Clarification: The given recurrence can be solved by using the second case of Master’s theorem.
T(n) = O(nc log n) = Here nc = n²
So the solution becomes T(n) = O(n²log n).

2. Solve the following recurrence using Master’s theorem.
T(n) = T (n/2) + 2ⁿ
a) T(n) = O(n²)
b) T(n) = O(n² log n)
c) T(n) = O(2ⁿ)
d) cannot be solved

Answer: c
Clarification: 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(n²log n)
d) T(n) = O(n²)
View Answer

Answer: d
Clarification: The given recurrence can be solved by using the first case of Master’s theorem. So the solution becomes T(n) = O(n²).

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(n²log n)
d) cannot be solved using master’s theorem

Answer: d
Clarification: 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(n²log n)
d) cannot be solved using master’s theorem

Answer: d
Clarification: 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(n²log n)
d) cannot be solved using master’s theorem
Answer: a
Clarification: 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)²)
b) T(n) = O(n log n)
c) T(n) = O(n²log n)
d) cannot be solved using master’s theorem

Answer: a
Clarification: 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)²).

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)
Answer: c
Clarification: 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)

Answer: d
Clarification: 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(n²)

Answer: a
Clarification: 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.