CODEWITHSUNDEEP
javaloopsfor-loopbig-onested-loops
Mike Neal
Mike Neal

Reputation: 31

Big O of nested for loop

int y = 1;
for (int x = 1 ; x <= n+2 ; x++)
  for (int w = n ; w > 0 ; w--)
    y = y + 1;

I'm a little confused about determining the BigO of the above code. If in the outermost loop it was for(int x = 1; x <= n; w++), then the BigO of the loop would be O(n^2) because the outermost loop would iterate n times and the innermost loop would also iterate n times.

However, given that the outermost loop iterates n+2 times, would that change the bigO or does the rule that additive constants don't matter imply? Lastly, would it change anything if the innermost loop were to iterate n+2 times instead of n?

Thank you!

Upvotes: 0

Views: 197

Answers (4)

YoungHobbit
YoungHobbit

Reputation: 13402

for (int x = 1 ; x <= n+2 ; x++)

outer loop is (n+2) times.

  for (int w = n ; w > 0 ; w--)

inner loop is (n) time

((n+2) * n) => n^2 + 2n => O(n^2). Because we consider the larger value.

The reason is for the larger values of n, value of 2n will be insignificant to n^2. So we drop the n.

You can read here for more explanation: Big O Analysis

Upvotes: 1

Andreas
Andreas

Reputation: 159175

Outer loop run n + 2 times, and inner loop runs n times, so code block runs (n + 2) * n times, which is n * n + 2 * n times. With increasing values of n, the 2 * n becomes insignificant, so you're left with n * n, giving you the answer: O(n^2)

Upvotes: 3

RoyBass
RoyBass

Reputation: 26

n and n+2 are the same order of magnitude, so this code run in O(n^2). Even if the inner loop runs n + 2 times.

Upvotes: 1

Brett Haines
Brett Haines

Reputation: 184

Long-ish answer short, the additive constants don't matter.

Suppose we did count the constants. Then, the inner loop is executed

(n+2)(n) = n^2 + 2n

times. This is still O(n^2), since the squared term takes precedence over the linear term.

Upvotes: 1

Related Questions