Logarithmic Runtime

Iterating powers of a number

Let’s analyze the loop below where we iterate over all powers of $2$

for (int i = 1; i <= N; i *= 2)
    x++;

• Iteration $1$: $i=1$
• Iteration $2$: $i=2$