CUET PG 2026 — DSA PYQ

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

Step 1: Change of variable

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

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

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

Step 2: Rename the function

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

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

Step 3: Apply Master Theorem on $S(m)$

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

• $a=2$

• $b=2$

• $f(m)=2^m$

Calculate $m^{{\log }_{b}a}$:

$$m^{{\log }_{2}2}=m^1=m$$

Since $f(m)=2^m$ grows exponentially faster than $m^{{\log }_{b}a}=m$, Case 3 of the Master Theorem applies:

$$S(m)=\Theta (f(m))=\Theta (2^m)$$

Step 4: Substitute back to $n$

Since $2^m=n$:

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

Correct Answer: (A) $\Theta (n)$