Понимание значения, которое переменная цикла принимает при экспоненциальном увеличении

Question

Я знаю, что временная сложность цикла, имеющего экспоненциально возрастающую переменную цикла, равна O (log (log (n))).

В следующем коде я принимаю значения 2, 2 ^ k, (2 ^ k) ^ k = 2 ^ k ^ 2, (2 ^ k ^ 2) ^ k = 2 ^ k ^ 3,…, 2 ^ k ^ logk (log (n)).Последний член должен быть меньше или равен n, и у нас есть 2 ^ k ^ logk (log (n)) = 2 ^ log (n) = n.

for (int i = 2; i <=n; i = pow(i, k))  
{
    // some O(1) expressions or statements
} 

Я не получаюкак окончательное значение i становится 2 ^ k ^ logk (log (n))?Как последовательность получает это общее значение математически?

Answer 1

Сначала давайте изменим код, чтобы явно отслеживать количество итераций с другой переменной j:

for (int i = 2, j=0; i <=n; j+=1, i = pow(i, k))  

Также давайте предположим, что на каком-то шаге условие i точно равно n. Это будет последняя итерация. Какое значение j будет на этом шаге?

Мы видим, что на протяжении итераций i всегда

i = 2^(k^j)

так на этом шаге

n = 2^(k^j)

Чтобы получить j, давайте сначала применим log2 к обеим сторонам:

log2(n) = k^j

и затем примените logk (т.е. log с основанием k) к обеим сторонам:

j = logk(log2(n))

Очевидно, точное совпадение i == n является редким случаем, но его отсутствие влияет только на общее число итераций на 1, что не влияет на big-O. Другими словами, последнее значение i не становится точно 2^(k^logk(log2(n))), т.е. n. Это становится чем-то вроде 2^(k^logk(floor(log2(n)))), но асимптотически это то же самое.