CODEWITHSUNDEEP
c++time-complexity
Kawan
Kawan

Reputation: 15

What is the time complexity of following code?

int count = 0;
    for (int i = N; i > 0; i /= 2) {
        for (int j = 0; j < i; j++) {
            count += 1;
        }
    }

I am not getting the right answer. My answer is O(NlogN) but right answer is O(N). can someone help me out?

Upvotes: 1

Views: 1662

Answers (1)

GustavD
GustavD

Reputation: 161

1 + 1/2 + 1/4 + 1/8 ... ~= 2 right?

So you go through each elements less than 2n times which is O(N)

Upvotes: 4

Related Questions