How does O(log log N) complexity loop look like?

Question

I have a very basic question here

for(int i = 1; i < N/2; i++) {

}

My initial understanding was the time-complexity for the above loop would O(logn) but after reading through some articles it is pretty much evident that it's simply O(n) and O(logn) would look like for (i = 1; i <= n; i *= 2)

Now my question is how does O(log log N) loop look like?

Answer 1

O(log n) loop:

for (i = 1; i <= n; i *= 2)

So you double i at each step. Basically:

1. Increment => O(n)
2. Doubling => O(log n)
3. ??? => O(log log n)

What comes after multiplication? Exponentiation. So this would be O(log log n):

for (i = 2; i <= n; i *= i) // we are squaring i at each step

Note: your loop is O(n), not O(log n). Keeping in line with the increment / double / exponentiate idea above, you can rewrite your loop using incrementation:

for(int i = 1; i < n; i += 2)

Even if you increment by more, it's still incrementation, and still O(n).