Skip to interview prep
Apexed

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).

What is the complexity of a loop where i doubles each time (i = 1, 2, 4, …, n) — Data structures & algorithms interview question — Apexed