CUET PG 2026 — DSA PYQ

Match the Recurrence Relation in List I with its Master Theorem asymptotic solution in List II:

List I (Recurrence)

• A. $T(n)=4T(n/2)+n$

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

• C. $T(n)=2T(n/2)+n$

• D. $T(n)=8T(n/2)+n^3$

List II (Master Theorem Solution)

1. $\Theta (N^3\log N)$ (Note: $N^3\log N$ formatted as $N3\log N$ in source)

2. $\Theta (N^2)$

3. $\Theta (\log N)$

4. $\Theta (N\log N)$