CUET PG 2026 — DSA PYQ

The Master Theorem form for divide-and-conquer recurrences is:

$$T(n)=aT(n/b)+f(n)$$

From the given recurrence relation $T(n)=4T(n/2)+n$:

• $a=4$

• $b=2$

• $f(n)=n$

Step 1: Calculate $n^{{\log }_{b}a}$

$$n^{{\log }_{b}a}=n^{{\log }_{2}4}=n^2$$

Step 2: Compare $f(n)$ with $n^{{\log }_{b}a}$

• $f(n)=n$

• $n^{{\log }_{b}a}=n^2$

Since $f(n)=O(n^{2-ϵ})$ for \epsilon = 1 > 0, $f(n)$ grows polynomially slower than $n^{{\log }_{b}a}$.

Step 3: Apply Case 1 of Master Theorem

If $f(n)=O(n^{{\log }_{b}a-ϵ})$, then:

$$T(n)=\Theta (n^{{\log }_{b}a})$$

Therefore:

$$T(n)=\Theta (n^2)$$

Correct Answer: (B) $\Theta (n^2)$