CODEWITHSUNDEEP
algorithmtime-complexitycomplexity-theory
A00
A00

Reputation: 3

Time complexity of dependent nested loops

I was trying to find the time complexity of this nested loop

for (i = 1; i <= n; i++) {
  for (j = 1; j <= n; j++) {
    n--;
    x++;
  }
}

If there wasn't a n-- it would be n*n , O(n2) right?

But what if n reduces every time second loop runs?

What's the time complexity and big O of this nested loop?

If I consider n = 5, x equals 4, the second loop runs 4 time

Upvotes: 0

Views: 272

Answers (2)

Kelly Bundy
Kelly Bundy

Reputation: 27609

Another way to see it's O(n): You only enter the inner loop body if j <= n, and since j is positive, n must also be positive. But you decrease n every time, which you can only do O(n) times (where n is the starting value) and still have n positive.

Upvotes: 0

David G
David G

Reputation: 96810

The time complexity of the code is O(n). n is reduced by half for every iteration of the outer loop.

So we have n/2 + n/4 + n/8 + n/16 + ... + n/2^k = O(n)

where k is the number of iterations of the outer loop (basically i).

Note that the time complexity is independent of x.

If there wasn't a n-- it would be n*n , O(n2) right?

Yes

Upvotes: 4

Related Questions