CODEWITHSUNDEEP
time-complexity
skjoshi
skjoshi

Reputation: 2533

Why does following code has complexity of O(n)?

I was going through some practice problem at this page. The question asks for the time complexity for below code and answer is O(n). However, as per my understanding outer loop runs log(n) times and inner one by O(n) thus it should have complexity of O(n*log(n)).

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

Please clarify what am I missing here.

Upvotes: 0

Views: 39

Answers (1)

user10316011
user10316011

Reputation:

The inner statement is run N + N/2 + N/4 + N/8 + ... times. Which is 2*N = O(N).

Upvotes: 5

Related Questions