Match List I with List II Choose the correct answer from the options given…

Concept: The Master theorem gives the exact growth rate of a divide-and-conquer recurrence T(n) = aT(n/b) + f(n) by comparing f(n) to n raised to the critical power (log base b of a): if f(n) grows strictly slower than that critical power, T(n) is exactly Θ of that critical power — Case 1; if f(n) grows at exactly that rate, T(n) is exactly Θ of that critical power times log n — Case 2. A subtractive recurrence such as T(n) = T(n-1) + c does not divide n at all, so the theorem does not apply — it is solved directly by unrolling, which gives T(n) = Θ(n).

Application:

1. (A): T(n) = 2T(n/2) + n — here a = 2, b = 2, so log2(2)=1 and the critical power is n1 = n. Since f(n) = n matches that rate exactly, Case 2 applies: T(n) = Θ(n log n) — an exact bound. This is (I).

2. (B): T(n) = T(n/2) + 1 — here a = 1, b = 2, so log2(1)=0 and the critical power is n0 = 1. Since f(n) = 1 matches that rate exactly, Case 2 applies: T(n) = Θ(log n) — exact, but List II has no exact Θ(log n) tag, so (B) needs one of the two loose O(...) tags instead (both O(n) and O(n2) are valid upper bounds for Θ(log n)).

3. (C): T(n) = 2T(n/2) + 1 — here a = 2, b = 2, so the critical power is again n1 = n. Since f(n) = 1 grows strictly slower than n, Case 1 applies: T(n) = Θ(n) — an exact bound. This is (III).

4. (D): T(n) = T(n-1) + 1 is subtractive, not divide-and-conquer, so the Master theorem does not apply. Unrolling gives T(n) = T(1) + (n-1)*1 = Θ(n). The exact Θ(n) tag (III) is already taken by (C), so (D) also needs one of the two loose O(...) tags instead (both O(n) and O(n2) are valid upper bounds for Θ(n) too).

Cross-check: List II offers exactly two exact-Θ tags: (I) for Θ(n log n) and (III) for Θ(n). Among the four recurrences, (A) is the one that resolves exactly to Θ(n log n) and (C) is the one that resolves exactly to Θ(n), so only (A)-(I) and (C)-(III) place these two exact tags correctly; every offered option that assigns either exact tag elsewhere is thereby ruled out. That leaves (B) and (D) to share the two loose tags, (II) and (IV) — both are valid upper bounds for either recurrence, so this particular pair cannot be resolved by growth-rate alone; it is fixed by checking which of the four offered permutations is otherwise self-consistent. Only one of the four offered options keeps both exact tags honest at all, so that option — the one pairing (B) with (IV) and (D) with (II) — is the correct match by elimination.

So the correct match is (A)-(I), (B)-(IV), (C)-(III), (D)-(II).