Find time complexity of a given nested loop

Question

What is the time complexity for this loop below?

int sum = 0;
for(int n = N; n > 0; n/=2)
    for(int i = 0; i < n; i++)
    sum++ 

I figured out that the inner loop runs N + N/2 + N/4 + N/8 + ... + 1 times, but now I don't know how to proceed. How do I get the tilde or big-O from this loop?

Thanks in advance.

Answer 1

Big-O from this loop is O(N) such as the dependence of the number of iterations on N is linear.

About 1/2 + 1/4 + 1/8 + ... https://en.wikipedia.org/wiki/1/2_%2B_1/4_%2B_1/8_%2B_1/16_%2B_%E2%8B%AF

About Big-O https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation

Answer 2

N + N/2 + N/4 + N/8 + ... + 1 forms a GP(geometric progress) which sums up to 2N. While defining time complexity in terms of big O, we discard the constant. So time complexity of your problem is O(N).