How to find the time complexity of nested for-loop

Question

What is the time complexity for the nested loops shown below:

1)

for (int i = 1; i <=n; i += 2) {
    for (int j = 1; j <=n; j += 2) {
        // some O(1) expressions
    }
}

2)

for (int i = 1; i <=n; i += 3) {
    for (int j = 1; j <=n; j += 3) {
        // some O(1) expressions
    }
}

In general:

for (int i = 1; i <=n; i += c) {
   for (int j = 1; j <=n; j += c) {
      // some O(1) expressions
   }
}

Is is really this the following?

O(nc)

Answer 1

Your algorithm will execute (n / c) * (n /c) iterations. We're dividing, because we are skipping c characters for each iteration. See that:

for (var i = 0; i <= n; i = i + 1)

Will have n / 1 iterations

for (var i = 0; i <= n; i = i + 2)

Will have n / 2 iterations

_{*Note that the result will be floored. That is, if n = 3 and c = 2, it will execute only one time (floor(3 / 2) == 1)}

So, we can generalize it to be

(n / c)2
= (n2/c2) 
= 1/c2 * n2

Remember that Big O is only interested in the rate of change. Since c is a constant, it is ignored from the calculation.

So, the result is:

O(1/c2 * n2) = O(n2)