Loop Iteration Count from the Update Rule (i+1 vs i2 vs ii)

The core idea

For a loop of the shape

i = i0;
while (i <= n) {
  /* O(1) body */
  i = f(i);
}

the running time is $\Theta(\text{number of iterations})$ when the body is $O(1)$. The iteration count is decided entirely by the update rule $i \leftarrow f(i)$. The recipe is always the same three steps:

1. Track the counter. Write $i_k$, the value of $i$ after $k$ executions of the body, as a closed form in $k$.
2. Find the stopping point. The body runs while $i_k \le n$; solve $i_k \le n$ for $k$.
3. Invert to get $k$. Whatever function grew $i$ is inverted to count the steps: repeated addition inverts to division, repeated multiplication inverts to a logarithm, repeated squaring inverts to a double logarithm.

The three update families

The pattern is a clean ladder: each time you make the update one operation "stronger" (add $\to$ multiply $\to$ square), you peel off one logarithm from the iteration count. Going the other way (e.g. $i \leftarrow \sqrt{i}$ shrinking down to a constant) also yields $\Theta(\log\log n)$ by the same inversion.

Why squaring gives $\log\log n$

Start at $i_0 = 2$ and square each step. The exponent doubles every iteration:

$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}},$

because $\left(2^{2^{k}}\right)^{2} = 2^{2^{k}\cdot 2} = 2^{2^{k+1}}$. The loop stops when

$2^{2^{k}} > n \quad\Longleftrightarrow\quad 2^{k} > \log_2 n \quad\Longleftrightarrow\quad k > \log_2\!\left(\log_2 n\right).$

Taking $\log_2$ once undoes the outer power; taking it a second time undoes the doubling of the exponent. So the number of iterations is $\Theta(\log\log n)$ — and since the body is $O(1)$, the total time is $\Theta(\log\log n)$.

How to apply it

• Read the update line, not the test. The comparison i <= n only tells you the bound; the growth speed comes from i = f(i).
• The starting value $i_0$ only changes lower-order constants. As long as $i_0 \ge 2$ for a multiplicative/squaring loop, the asymptotic order is unchanged. (Beware $i_0 = 1$ with i = i*i — it never grows: $1\cdot1=1$ — an infinite loop, a classic trap.)
• For nested loops, multiply the per-loop counts. A *2 outer loop wrapping a +1 inner loop is $\Theta(n\log n)$, etc.

Worked mini-example

How many times does the body run?

i = 2;
while (i <= n) { i = i * i; }

The update is squaring, so $i_k = 2^{2^{k}}$. It stops when $2^{2^{k}} > n$, i.e. $k > \log_2 \log_2 n$. Hence the body runs $\Theta(\log\log n)$ times and the loop is $\Theta(\log\log n)$. Contrast the same loop bound with a multiplicative update i = i * 2, which would give $i_k = 2^{k+1}$, stopping at $k \approx \log_2 n$ — an exponentially larger $\Theta(\log n)$ — showing how much the single update operator matters.

Exam trick: Don't be fooled by i <= n into guessing $\Theta(n)$. Identify the update operator: + $\Rightarrow \Theta(n)$, \times $\Rightarrow \Theta(\log n)$, squaring $\Rightarrow \Theta(\log\log n)$. Each step up in operator strength removes one $\log$.