Master Theorem Interview Questions and Answers

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) + 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: c
Explanation: 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
View Answer

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

Answer: d
Explanation: 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
View Answer

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

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

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

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

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

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

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

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

« Prev - Master Theorem Multiple Choice Questions and Answers

» Next - Fractional Knapsack Problem Multiple Choice Questions and Answers (MCQs)

Related Posts:

Recommended Articles: