CODEWITHSUNDEEP
runtimebig-o
PTN
PTN

Reputation: 1692

Runtime of nested for loops is O(n^2)?

I have these nested loops

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

The outer loop throws me off a little bit. Is the runtime still O(n^2) or it's something else?

Upvotes: 1

Views: 313

Answers (1)

hardik pandey
hardik pandey

Reputation: 21

Here the inner loop executes 1 + 2 + ... + n/2 + n times. It has lg n terms in this sequence, and that does mean that int i = 0 executes lg n times,

The sum for the statement(s) in the inner loop is 2n. So we get O(n + lg n) = O(n)

Upvotes: 2

Related Questions