Time complexity for inner loop

Question

What's the time complexity for this code?

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
    }
  }
}

The first loop is n. The second loop is n - i And the third one is n - j.

I and J are the same. So the interesting is in the second and third loops. The gcd is going to work everytime i and j are different. So J is going to really work only like "once" per loop, so we can say j loop is constant. And K is going to be like (n-j) times, so (n - j) * n = n^2. So my guess is that the time complexity is O(n^2).

What do you think?

Answer 1

The time complexity of the innermost loop is proportional to $n-j+1$.

Then, assuming that the assignment $j:=i$ indeed causes a loop exit, the intermediate loop executes at most twice every time it is entered, for $j = i$, and possibly $j=i+1$.

So the total cost is proportional to $(n+n-1)+(n-1+n-2)+\cdots (2+1)+1=n^2$.