# Time complexity for inner loop

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?

• Your thinking seems to be right, but your wording of it looks insufferably sloppy to me -- in particular you keep abusing the word "is" to mean things it really can't support. Don't say that a loop "is $n-j$" when you mean that the loop "executes $n-j$ iterations", and don't say "is constant" for "executes a constant number of iterations". – Henning Makholm May 2 '16 at 12:33
• Also (in comment to my confusion which led to my wrong -- now deleted -- answer): who did write this? This code is horrendously confusing: if the goal is to have the value that $j$ takes be only $i$, why add an inner "for" loop with a further test that changes the variable's value (not very clean practice)? This looks like obfuscation more than good practice. – Clement C. May 2 '16 at 12:35
• Thanks for the corrections Henning. I'll try to be more careful with my wording. – Manuel May 2 '16 at 12:36
• @ClementC. It's a code for analysis of loop's time complexity. It's made on purpose to be confusing. It only has academical use. – Manuel May 2 '16 at 12:38
• The j=n would be a stinker in production code, except perhaps if you're writing in an extremely restricted language that doesn't provide a more explicit way to break out a loop. In pseudocode it is a complete and total abomination that should never be written down in that way. – Henning Makholm May 2 '16 at 12:39

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$.
• @ClementC was right to worry about the cost of GCD computation. Quite logically, only a constant number of Euclidean iterations will be performed per invocation. Unless the GCD algorithm used is subtraction- rather than division-based, and will require like $i+1$ subtractions when $j=i+1$. Fortunately, this doesn't increase the asymptotic complexity. – Yves Daoust May 2 '16 at 13:03