What is the big-O of this for loop...?-CodePudding

The first loop runs O(log n) time but the second loop's runtime depends on the counter of the first loop, If we examine it more it should run like (1 2 4 8 16.... N) I just couldn't find a reasonable answer to this series...

for (int i = 1; i < n; i = i * 2)
{
    for (int j = 1; j < i; j  )
    {
        //const time
    }
}

CodePudding user response：

Just like you said. If N is power of two, then 1 2 4 8 16.... N is exactly 2*N-1 (sum of geometric series) . This is same as O(N) that can be simplified to N.

CodePudding user response：

It is like :

1 2 4 8 16 .... N

= 2 ^ [O(log(N) 1] - 1

= O(N)