CUET PG 2026 — DSA PYQ

The general form for the Master Theorem recurrence relation is:

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

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

• $a=1$

• $b=2$

• $f(n)=1=\Theta (n^0)$

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

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

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

• $f(n)=1$

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

Since $f(n)=\Theta (n^{{\log }_{b}a})$, both $f(n)$ and $n^{{\log }_{b}a}$ grow at the same rate.

Step 3: Apply Case 2 of the Master Theorem

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

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

Substituting $n^{{\log }_{b}a}=1$:

$$T(n)=\Theta (1\cdot \log n)=\Theta (\log n)$$

Correct Answer: (C) $\Theta (\log n)$