0

Assuming we have the following loop:

O(N) Loop

for (int i = 1; i <=n; i *= c) {
   // some O(1) expressions
}

O(LogLogN) Loop

for (int i = 2; i <=n; i = pow(i, c)) { 
   // some O(1) expressions
}

For the O(LogLogN) Loop, we have:

Iteration [1] -> 2^(2^0)
Iteration [2] -> 2^(2^1)
Iteration [3] -> 2^(2^2)
Iteration [4] -> 2^(2^3)

Since 2^n is O(LogN), we can replace the above as 2^(2^k), or 2^c. As c is O(LogN), we can deduce that 2^c is O(LogLogN).

Am I on the right track?

  • Does this answer your question? [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – Mark Rotteveel Mar 05 '22 at 11:15

0 Answers0