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））です