What is the time complexity of this code that has 3 nested loops but j stops when it's equal to i * 2?

Bi Bi 0
Viewed 42
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];  //O(1)
      }
      if (j == 2 * i) {
         j = n;
      }
   }
}

I've spent so many hours tracing the code and tried different n values. I realize that j doesn't run more than [n/2 + 1] times. I made a table that looks like this for n = 8, 9, 12.

(Apologies for the picture, I am new to Stack Overflow) i and j are values of i and j, whereas the k is the number of times that innermost loop runs

So it turns into something like: [n+(n-1)] + [(n-1)+(n-2)+(n-3)] + [(n-2)+(n-3)+(n-4)+(n-5)] + ...+ [3+2+1] + [2+1] + 1

I'm not sure how to put this into a arithmetic progression or summation. Please help.

analysis time-complexity algorithm
1 Answers

There's n-j work in the inner loop. For any particular value of j, there's approximately j/2 + 1 possible values of i. For example j can take the value 10 when i is 5,6,7,8,9 or 10.

So the total time complexity is sum((j/2+1) * (n-j), j=1..n), which is n^3/12+n^2/2-7/12 = O(n^3)

I've been sloppy with rounding here, but it doesn't affect the complexity.

Paul Hankin0
Related