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

The loop variable starts at $i=2$ and is squared every iteration ($i = i \cdot i$), so it grows much faster than the usual doubling.

Track the value of $i$. After $k$ iterations of the body, the value is

$i_0 = 2,\quad i_1 = 2^{2},\quad i_2 = 2^{4},\quad i_3 = 2^{8},\ \dots,\quad i_k = 2^{2^{k}}.$

Each step doubles the exponent, because $\left(2^{2^{k}}\right)^{2} = 2^{2^{k}\cdot 2} = 2^{2^{k+1}}$.

Find when the loop stops. The body runs while $i \le n$, i.e. while

$2^{2^{k}} \le n.$

Take $\log_2$ once:

$2^{k} \le \log_2 n.$

Take $\log_2$ again:

$k \le \log_2\left(\log_2 n\right).$

So the number of iterations is $\Theta(\log\log n)$. Each iteration does $O(1)$ work, giving total running time

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

The answer is option 4.

Exam trick: A loop with $i = i+1$ runs $\Theta(n)$ times, $i = i \cdot 2$ (geometric growth) runs $\Theta(\log n)$ times, and $i = i \cdot i$ (repeated squaring) runs $\Theta(\log\log n)$ times. Squaring applies $\log$ twice.