CODEWITHSUNDEEP
algorithm
Ergysi RM
Ergysi RM

Reputation: 15

Find the time complexity of the algorithm?

I think it is log(logn) because the cycle repeats log(logn) times...

j=1;
i=2;
while (i <= n) do {
    B[j] = A[i];
    j = j + 1;
    i = i * i;
}

Upvotes: 0

Views: 37

Answers (1)

Leandro Caniglia
Leandro Caniglia

Reputation: 14858

You are right, it is O(lg(lg n)) where lg stands for base 2 logarithm.

The reason being that the sequence of values of i is subject to the rule i = prev(i) * prev(i), which turns out to be 2, 2^2, 2^4, 2^8, ... for steps 1, 2, 3, 4, .... In other words, the value of i after k iterations is 2^{2^k}.

Thus, the loop will stop as soon as 2^{2^k} > n or k > lg(lg(n)) (Just take lg twice to both sides of the inequality. The inequality remains valid because lg is an increasing function.)

Upvotes: 2

Related Questions