while-loop - 这个while循环的时间复杂度？

Question

这个循环的时间复杂度是多少？

j=2
while(j <= n)
{
    //body of the loop is Θ(1)
    j=j^2
}

Answer 1

你有

j = 2

每个循环：j = j^2

模式是：

2     = 2^(2^0)
2*2   = 2^(2^1)
4*4   = 2^(2^2)
16*16 = 2^(2^3)

可以看作：

2^(2^k) with k being the number of iteration

因此循环在 时停止：

2^(2^k) >= n
log2(2^(2^k)) >= log2(n)
2^k >= log2(n)
log2(2^k) >= log2(n)
k >= log2(log2(n))

复杂度为 log2(log2(n))