5. What is the complexity of a loop where i doubles each time (i = 1, 2, 4, …, n)?
EasyAlgorithm analysis
Technical
Show model answer
The loop runs about log₂ n times, so it is O(log n). Nested loops multiply: an outer loop of n iterations around this inner loop is O(n log n). A loop with i *= 2 inside a loop with j++ up to i sums to 1 + 2 + 4 + … + n = O(n).