CUET PG 2026 — DSA PYQ

To solve the recurrence $T(n)=T(\sqrt{n})+1$, we use domain transformation:

Step 1: Substitution / Change of variable

Let $n=2^m$, which means $m={\log }_{2}n$.

Since $\sqrt{n}=n^{1/2}=(2^m{)}^{1/2}=2^{m/2}$, substitute this into the recurrence relation:

$$T(2^m)=T(2^{m/2})+1$$

Step 2: Rename the function

Let $S(m)=T(2^m)$. The equation becomes:

$$S(m)=S(m/2)+1$$

Step 3: Solve $S(m)$ using Master Theorem

For $S(m)=aS(m/b)+f(m)$:

• $a=1$

• $b=2$

• $f(m)=1$

Calculate $m^{{\log }_{b}a}=m^{{\log }_{2}1}=m^0=1$.

Since $f(m)=\Theta (1)=\Theta (m^{{\log }_{b}a})$, by Case 2 of the Master Theorem:

$$S(m)=\Theta (\log m)=O(\log m)$$

Step 4: Substitute back to $n$

Since $m={\log }_{2}n$:

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

Correct Answer: (D) $O(\log \log n)$