Time Complexity (3 loops with gcd)

Question

for (int i = 1 to n) {
    for(int j = i to n) {
        for(int k = j to n) {
            Sum += a[i] * b[j] * c[k]
        }
        if (gcd(i, j) == 1) {
            j = n
        }
    }
}

Answer 1

Normally, these three loops runs O(n) respectively, making the time complexity O(n²).

However, consider the second loop, where there is

    If (gcd(i,j) == 1) {

      j = n

    }

Then, since there is gcd(i,j) == 1, the loop ends. Since the GCD of any two consecutive integer is 1, the second loop would always ends when j == i + 1. Thus, the second loop runs O(1) times only.

As a result, the time complexity isT(n) = O(n²)