Master Theorem MCQs: 12 Solved Questions with Explanations

The Master Theorem quickly solves divide-and-conquer recurrences, but it is easy to misuse. Ten of these twelve questions carry named exam attributions from GATE, Coal India, UGC NET, or ISRO; the other two are concept questions. Attempt each before reviewing the explanation in the Algorithms section.

What the Master Theorem actually covers

Use the reference form T(n) = aT(n/b) + f(n), where a >= 1 and b > 1 are constants and f(n) is asymptotically positive. Compare f(n) with the yardstick n^(log_b a). For cases 1 and 3, the difference must be polynomial, not merely a logarithmic factor.

Q1. What does the theorem solve?

What does Master theorem solve?

• (a) Recurrence relations for Divide and Conquer algorithms

• (b) Complexity of Brute Force algorithms

• (c) Complexity of Greedy algorithms

• (d) Recursion

Answer: (a). The theorem directly solves recurrences of the form aT(n/b) + f(n), which divide-and-conquer algorithms produce. It does not cover recursion in general. A recurrence with T(n-1), for example, does not fit.

Q2. Which recurrence can use it?

Coal India 2017 asks: Which of the following recurrence relation can be solved using Master theorem?

• (a) T(n) = 64T(n/8) − n

• (b) T(n) = 2T(n/2) + n/(log n)

• (c) T(n) = 2ⁿT(n/2) + n

• (d) T(n) = 2T(n/2) + 1

Answer: (d). In (a), f(n) = -n is negative. In (c), a = 2ⁿ is not constant. In (b), n/log n is below the yardstick n only by a logarithmic factor, so no standard case fires. For (d), a = b = 2 and f(n) = 1. Case 1 gives T(n) = Θ(n).

Case 1: the leaves dominate

Q3. Growing work at each level

Coal India 2020 recurrence:

T(n) = 4T(n/2) + n

• (a) O(n²)

• (b) O(n/2)

• (c) O(n)

• (d) O(log n)

Answer: (a). Here a = 4, b = 2, and n^(log_2 4) = n². Since f(n) = n, choose ε = 1 and apply case 1 to get Θ(n²).

The recursion tree confirms the case. Level i contributes 2^i n, so work doubles down the tree. With n² unit-cost leaves, the total is n(1 + 2 + ... + n) = 2n² - n. For n = 8, the levels sum to 8 + 16 + 32 + 64 = 120.

Q4. A logarithmic root cost

GATE 2014 asks: Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1? T(n) = 2T(n/2) + log n.

• (a) Θ(n)

• (b) Θ(n log n)

• (c) Θ(n²)

• (d) Θ(log n)

Answer: (a). The yardstick is n. Because log n is polynomially smaller, case 1 gives Θ(n). Merge sort instead has f(n) = n and gives n log n; compare the recurrences in Sorting Algorithms: Complexity and Comparison.

Case 2: root and leaves tie

Q5. One changed term, one changed case

Coal India 2020 recurrence:

T(n) = 4T(n/2) + n²

• (a) Θ(n³)

• (b) Θ(n² log n)

• (c) Θ(n²/2)

• (d) Θ(n²)

Answer: (b). As in Q3, a = 4, b = 2, and the yardstick is n². This time f(n) = n² matches it, so case 2 gives Θ(n² log n). Every level does n² work because 4 subproblems of size n/2 contribute 4(n/2)² = n².

Q6. Read the logarithm base carefully

UGC NET June 2025 asks: The tight asymptotic bound for T(n) = 2T(n/4) + √n is:

• (a) Θ(√n)

• (b) Θ(n log n)

• (c) Θ(√n log n)

• (d) Θ(n log √n)

Answer: (c). Here log_4 2 = 1/2 because 4^(1/2) = 2. Therefore, the yardstick is √n, exactly matching f(n). Case 2 gives Θ(√n log n).

Case 3: the root dominates

Q7. Check polynomial dominance

GATE 1996 asks: The recurrence relation T(1) = 2,

T(n) = 3T(n/4) + n

• (a) O(n)

• (b) O(log n)

• (c) O(n^(3/4))

• (d) None of the above

Answer: (a). The yardstick is n^(log_4 3), approximately n^0.79. Since f(n) = n is polynomially larger, case 3 is possible. Regularity also passes: 3f(n/4) = 3n/4 = (3/4)f(n), with c = 3/4. Thus T(n) = Θ(n), hence O(n). The exponent log_4 3 is not 3/4.

Q8. Do the regularity algebra

UGC NET June 2022 asks: The solution of T(n) = 3T(n/4) + n lg n is:

• (a) Θ(n² lg n)

• (b) Θ(n lg n)

• (c) Θ(n lg n)²

• (d) Θ(n lg lg n)

Answer: (b). The yardstick remains about n^0.79, while f(n) = n lg n is polynomially larger. Also, 3f(n/4) = 3(n/4)lg(n/4) = (3/4)n(lg n - 2) <= (3/4)n lg n. Regularity passes with c = 3/4, so T(n) = Θ(n lg n). Option (c) is printed as Θ(n lg n)² and reads as (n lg n)².

Gap cases, extended case 2, and floors

Q9. One log above the yardstick

This concept question asks: What is the tight asymptotic time complexity (the best upper bound, Θ) of the following recurrence relation?

T(n) = 2T(n/2) + n log n, for n >= 2

T(1) = 0

• (a) O(n (log n)²)

• (b) O(n)

• (c) O(n log n)

• (d) O(n²)

Answer: (a). The yardstick is n. The extra log n is not a polynomial gap, so extended case 2 gives Θ(n log² n), represented by option (a). For Q2(b), summing n/(log n - i) across the levels gives Θ(n log log n); the Θ(n) leaves do not change that bound.

Q10. The floor changes nothing

UGC NET June 2014 asks: The solution of the recurrence relation of T(n) = 3T(⌊n/4⌋) + n is:

• (a) O(n²)

• (b) O(n lg n)

• (c) O(n)

• (d) O(lg n)

Answer: (c). This is Q7 with a floor. The theorem absorbs floors and ceilings, so the same case-3 analysis gives Θ(n), hence O(n).

When the form does not fit: change the variable

Q11. Turn square roots into halving

Indian Space Research Organization 2016 asks: Consider the following recurrence: T(n) = 2T(√n) + 1, with T(1) = 1. Which of the following is true?

• (a) T(n) = O(log log n)

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

• (c) T(n) = O(√n)

• (d) T(n) = O(n)

Answer: (b). Put n = 2^m. Then T(2^m) = 2T(2^(m/2)) + 1, so S(m) = 2S(m/2) + 1. Case 1 gives S(m) = Θ(m). Since m = log n, T(n) = Θ(log n). Option (a) would fit T(n) = T(√n) + 1, where the coefficient is 1.

Ranking recurrences: solve, then sort

Q12. Rank five recurrence relations

UGC NET August 2024 asks: Arrange the following recurrence relations in increasing order of their time capacity.

• (A) T(n) = T(n/2) + 1

• (B) T(n) = 2T(n/2) + n

• (C) T(n) = 3T(n/3) + n

• (D) T(n) = 2T(n/2) + n

• (E) T(n) = T(n-1) + 1

• (a) (E), (A), (B), (D), (C)

• (b) (A), (E), (D), (B), (C)

• (c) (E), (A), (D), (B), (C)

• (d) (A), (B), (D), (E), (C)

Answer: (b). The paper uses "time capacity" for time complexity and prints (B) and (D) identically. Recurrence (A) is Θ(log n), (E) is Θ(n) by unrolling, and (B), (C), and (D) are Θ(n log n). Thus only option (b) respects log n < n < n log n. For bound semantics, use Asymptotic Notations MCQs: 12 Solved Questions.

The short version and your next step

• Write a, b, f(n), and n^(log_b a) before choosing a case.

• Case 1 favours the leaves, case 2 adds a log, and case 3 needs the regularity check.

• Use extended case 2 for log-factor gaps; transform T(√n) before applying the theorem.

KnowledgeGate's practice bank has about 40 Master Theorem questions. Full worked solutions are available in GATE Guidance by Sanchit Sir. Continue there, or browse the wider GATE CS Exam Preparation catalogue.