I’m trying to determine the time complexity of the following code snippet, but I’m unsure about how to correctly sum the iterations of the inner loop:

k = 1
for i <- 1 to n
 for j = 1, j < n/k , j++
   print
 k = 2k

In this code, k doubles after each iteration of the outer loop. Here’s my reasoning:

The outer loop runs n times, so initially, it seems to have a complexity of O(n)
The inner loop iterates n/k times for each value of k, which doubles each time (k = 1, 2, 4, 8, …). The total number of iterations for the inner loop across all outer loop iterations can be represented as the series n+n/2+n/4+n/8+…
This series is a geometric series, and the sum converges to 2n. Given this, the total work done appears to be proportional to 2n, suggesting a linear complexity.

Question: Have I misunderstood something in calculating the series sum, or why does this not result in a complexity of O(n^2) as it initially appeared? Can someone clarify the correct time complexity for this code?