# Running time of this Program

def f(n):
i = 2
while i < n:
print(i)
i = i * i


I evaluated an expression that becomes something like 2^n or 2^2^n and set that equal to when the loop breaks or (2^2^n ) (>=)n but can't figure out how to get a runtime. Can someone show how to do complete this analysis and get a runtime?

In the loop, $i$ is repeatedly squared so it will take the values $$2, 2^2=4, 4^2=16, 16^2=258, \dotsc$$ In other words, $i$ will be $$2^1, 2^2, 2^4, 2^8, \dots,2^{2^k}$$ so the loop will iterate $k$ times, until $2^{2^k}\ge n$. Taking the log of this inequality twice we'll have $k\ge \log \log n$ for our running time.