0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.