CODEWITHSUNDEEP
c++big-o
ammar albakri
ammar albakri

Reputation: 78

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

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
    }
}

Upvotes: 1

Views: 94

Answers (2)

Mojtaba Valizadeh
Mojtaba Valizadeh

Reputation: 766

It is like :

1 + 2 + 4 + 8 + 16 + ....+ N

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

= O(N)

Upvotes: 2

Luka Rahne
Luka Rahne

Reputation: 10447

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.

Upvotes: 4

Related Questions