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

Сначала давайте изменим код, чтобы явно отслеживать количество итераций с другой переменной 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)

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

log2(n) = k^j

, а затем применим logk (то есть log с основанием k) к обеим сторонам: [ 1126]

j = logk(log2(n))

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