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

The question asks for the order of the value printed (the output j), not the running time.

Trace the loop. The variable i starts at $1$ and is multiplied by $4$ each pass, so it takes the values

$i = 1, 4, 16, \dots, 4^{k}, \dots$

The loop continues while $i \le n$, i.e. while $4^{k} \le n$. Let $K = \lfloor \log_4 n \rfloor$ be the largest such exponent.

Accumulate j. Each iteration adds $2i = 2\cdot 4^{k}$, so

$j = \sum_{k=0}^{K} 2\cdot 4^{k} = 2\cdot\frac{4^{K+1}-1}{4-1} = \frac{2}{3}\left(4^{K+1}-1\right).$

This is a geometric sum dominated by its last term, so $j = \Theta(4^{K})$.

Relate $4^{K}$ to $n$. By definition of $K$ we have $4^{K} \le n < 4^{K+1}$, hence

$\frac{n}{4} < 4^{K} \le n \quad\Longrightarrow\quad 4^{K} = \Theta(n).$

Therefore

$j = \Theta(4^{K}) = \Theta(n).$

The printed value grows linearly in $n$, so the answer is $\Theta(n)$ — option 1.

Exam trick: A geometric series with ratio $>1$ equals $\Theta(\text{largest term})$. Here the largest term $2\cdot 4^{K}$ is itself $\Theta(n)$, so you never need to count iterations — only the magnitude of the final term matters. (The number of iterations is $\Theta(\log n)$, which would be the running time; do not confuse it with the output value.)