Match List - I with List - II.

List - I (Recurrence Relations)	List - II (Complexity)
(A) $T(n)=2T(n/2)+n$	(I) $T(n)=\theta(n\log n)$ [exact solution]
(B) $T(n)=T(n/2)+1$	(II) $O(n^2)$
(C) $T(n)=2T(n/2)+1$	(III) $T(n)=\theta(n)$ [exact solution]
(D) $T(n)=T(n-1)+1$	(IV) $O(\log n)$

Choose the correct answer from the options given below :

(A) $T(n)=2T(n/2)+n$

Master theorem

$a=2,; b=2,; f(n)=n$

$\Rightarrow T(n)=\theta(n\log n)$

So (A) → (I)

(B) $T(n)=T(n/2)+1$

Divide size halves each step

$\Rightarrow T(n)=O(\log n)$

So (B) → (IV)

(C) $T(n)=2T(n/2)+1$

Master theorem

$\Rightarrow T(n)=\theta(n)$

So (C) → (III)

(D) $T(n)=T(n-1)+1$

Linear recurrence

$\Rightarrow T(n)=O(n)$

Closest option given:

(D) → (II)

Thus matching:

(A)-(I), (B)-(IV), (C)-(III), (D)-(II)