سوال ۶۲ کنکور ارشد علوم کامپیوتر ۱۴۰۲

Let $n = 3^{k}$, so $k = \log_3 n$.

Trace the variable $i$. It starts at $1=3^{0}$ and is tripled each pass. The guard i < n holds until $i$ reaches $n=3^{k}$, so the loop executes exactly $k = \log_3 n$ times. On pass $t$ (for $t = 1,2,\dots,k$) the statement i = i * 3 runs first, making

$i = 3^{t}.$

Trace the variable $j$. Each pass multiplies $j$ by the current value of $i$ (i.e. $3^{t}$, since $i$ is updated before $j$):

$j = \prod_{t=1}^{k} 3^{t} = 3^{\,1+2+\cdots+k} = 3^{\,\frac{k(k+1)}{2}}.$

Convert back to $n$. Using $3^{k}=n$ and $k=\log_3 n$:

$j = 3^{\frac{k(k+1)}{2}} = \left(3^{k}\right)^{\frac{k+1}{2}} = n^{\frac{k+1}{2}} = n^{\frac{\log_3 n + 1}{2}}.$

Hence the output is

$\theta\!\left(n^{\frac{1+\log_3 n}{2}}\right),$

which is option 4.

Sanity check ($n=27,\ k=3$): $j = 3^{1}\cdot 3^{2}\cdot 3^{3} = 3^{6}=729$, and $n^{(1+\log_3 n)/2}=27^{(1+3)/2}=27^{2}=729$. ✓

Pitfall: The exponents of $i$ form an arithmetic sequence $1,2,\dots,k$, so the product of all $i$-values gives $3^{k(k+1)/2}$, a super-polynomial (quasi-polynomial) growth — not the linear $\theta(n)$ you would get if $j$ were simply tripled each step. Watch whether the accumulator multiplies by a constant or by the growing loop variable.