Big O calculation confused

Question

I have this question for my exam, and I could not figure it out: calculate the Big O for the following:

1)

 for i = 0 to n     // n - 0 + 2 = (n+2)
  for j = 0 to m    // m - 0 + 2 = (m+2)
   x = x + 1

so does the answer become (n+2)(m+2) with O(nm) as the bigO?

Answer 1

it is O(nm)

I don't think your initial math is correct though

because you have (n+1)(m+1) but after you expand this you will get something like m*n+m+n+1 and since m*n is the highest order here you will get O(m*n)

Answer 2

so does the answer become (n+2)(m+2) with O(nm) as the bigO?

Why n+2? It would be n+1 if 0 to n contains n, or it would be n, if n is exclusive. Therefore run time would me (n+1)(m+1) or (nm).

However, O(nm) would be in all cases.

Answer 3

yes.

You have 2 loops. So you have O(outer * inner). The outer loop is executed about n times. The inner loop is executed bout m times.

So O(nm) is appropriate.