I was wondering about the time complexity of something like the following loop (where
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.