关于i=i*i+i递增的for循环时间复杂度的分析与求解问询

Great question! Let's walk through each part clearly, using your example sequence (quick note: 42*42 + 42 is 1806, not 1086—small typo there!)

1. What's the significance of i*i + i for time complexity? #

This expression defines how fast your loop variable i grows with each iteration. Unlike linear increments (like i++) or even linear-multiplicative steps (like i *= 2), this update rule makes i grow extremely quickly—almost quadratically each time (since i*i + i = i*(i+1), which is barely different from i² once i gets large).

The rate of growth directly determines how many times the loop runs: faster growth means fewer iterations, which translates to a lower overall time complexity. Since time complexity counts the total number of operations performed (assuming each loop iteration is O(1)), this update rule is the core factor driving the loop's complexity.

2. What's the big-O time complexity of this loop? #

It's O(log log n).

The sequence of i values grows so rapidly that even for very large n, the number of iterations stays tiny. For example, to reach n = 10^100, you'd only need about 5 iterations (2 → 6 → 42 → 1806 → ~3.26 million → ~10^13). The number of steps scales with the double logarithm of n, hence the O(log log n) complexity.

3. How to calculate big-O for this kind of incrementing index? #

Here's a step-by-step method you can apply to any non-linear loop increment:

• Step 1: Simplify the recurrence relation
  Ignore lower-order terms to make the math manageable. For i_{k+1} = i_k * i_k + i_k, when i_k is large, the i_k term is negligible compared to i_k², so we can approximate this as i_{k+1} ≈ i_k².

• Step 2: Iterate to find a closed-form approximation
  Start with your initial value i_0 = 2:

  • i_1 ≈ 2² = 2^(2^1)
  • i_2 ≈ (2²)² = 2^(2^2)
  • i_3 ≈ (2^(2^2))² = 2^(2^3)
  • ...
  • After k iterations: i_k ≈ 2^(2^k)

• Step 3: Solve for k (number of iterations) relative to n
  The loop stops when i_k >= n. Set our approximation equal to n and solve for k:

  1. 2^(2^k) ≈ n
  2. Take the base-2 logarithm of both sides: 2^k ≈ log₂(n)
  3. Take the base-2 logarithm again: k ≈ log₂(log₂(n))

  Since k is the total number of iterations, the time complexity is O(log log n). Even if you use the exact recurrence i_{k+1} = i_k(i_k +1), the asymptotic complexity stays the same—lower-order terms don't change the big-O result.

内容的提问来源于stack exchange，提问作者GccGUY