# Time complexity of linear iteration bounded by logarithmic iteration?

I was wondering about the time complexity of something like the following loop (where work() is O(1)):

for (i = 0 to N; i = i * 2) do
for(j = 0 to i; j = j + 1) do
work()
end
end


The outer loop takes $$\lg(N)$$ steps, and the inner loop takes (on the final iteration) $$N$$ steps. So, a simple bound would be $$O(N\lg(N))$$. However, the inner loop doesn't fully reach $$N$$ until the last iteration, so I was wondering if the bound could be narrowed any further.

Derp, nevermind. I observed that on the last iteration, the inner loop takes $$N$$ steps. On the previous iteration, the inner loop would take $$\frac{N}{2}$$ steps. Overall, this would take $$N, \frac{N}{2}, \frac{N}{4}, \frac{N}{8},...$$ steps, which has a geometric sum to $$2N$$ steps. Therefore, the loop is $$O(N)$$.