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?

  • 1
    $\begingroup$ 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". $\endgroup$ – Henning Makholm May 2 '16 at 12:33
  • $\begingroup$ 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. $\endgroup$ – Clement C. May 2 '16 at 12:35
  • $\begingroup$ Thanks for the corrections Henning. I'll try to be more careful with my wording. $\endgroup$ – Manuel May 2 '16 at 12:36
  • $\begingroup$ @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. $\endgroup$ – Manuel May 2 '16 at 12:38
  • 1
    $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ @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. $\endgroup$ – Yves Daoust May 2 '16 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.