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

1. Solve the following recurrence using Master’s theorem.

T(n) = 4T (n/2) + n^{2}

a) T(n) = O(n)

b) T(n) = O(log n)

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

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

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 = n

^{2}

So the solution becomes T(n) = O(n

^{2}log n).

2. Solve the following recurrence using Master’s theorem.

T(n) = T (n/2) + 2^{n}

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

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

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

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(n^{2}log n)

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

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(n

^{2}).

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^{2}log 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(n^{2}log 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(n^{2}log 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(n^{2}log 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(n^{2})

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__.