1

If the following loop structure is under Analysis of Upper bound, does it still compute to O(n^2)? I'm confused since inner loop has a dependency on the outer loop and with each outer iteration, the inner for loop loops one less time. In addition to whatever O(n) is, will the time complexity function be "n!.n+C" where C is a constant? I'm assuming n! because of inner loop.

for(int i=n;i>0;i--)
{
 for(int j=i;j>=1;j--)
  {
     count++;
  }
}
n. m. could be an AI
  • 112,515
  • 14
  • 128
  • 243
Syed Zainullah Qazi
  • 25
  • 4
  • Run this code for several `n`, say n = 1,2,...,15 and print `count`, and you'll see the answer. Or simplify the inner loop to `count += i` and you'll get much closer to the answer. You may then also want to simplify the outer loop to something like `1 + 2 + ... + n`, which is an arithmetic sequence, known to sum up to `n*(n+1)/2`, which is the final formula for the two loops being simplified to the very end. – zkoza Oct 20 '21 at 23:23
  • 2
    *I'm confused since inner loop has a dependency on the outer loop and with each outer iteration inner for loop loops one less time.* -- One less time is going to be worth absolutely nothing in terms of complexity -- this will still be `n^2`. Pretend `n` is a million, and not something small like 10 or 20 to conceptualize this. Reduce the number of times by half on each iteration (like for binary search), then you're talking a different thing altogether. – PaulMcKenzie Oct 21 '21 at 00:59

2 Answers2

6

This code has the same time complexity as the code in the question.

for(int i = 0; i < n; i++){  // outer loop
    for(int j = 0; j < i; j++){  // inner loop
        count++;
    }
}

In the first iteration of the outer loop (i = 0), the inner loop doesn’t execute.

In the second iteration of the outer loop (i = 1), the inner loop executes once.

In the third iteration of the outer loop (i = 2), the inner loop executes twice.

So, in the last iteration of the outer loop (i = n), the inner loop executes n times.

Therefore, the total number of times this code executes is

1 + 2 + 3 + … + n

= n(n + 1) / 2 (Sum of Natural Numbers Formula)

= ((n^2) + n) / 2

= O(n^2)

——————

Also, do take a look at these

  1. https://stackoverflow.com/a/71805214/17112163
  2. https://stackoverflow.com/a/71537431/17112163
  3. https://stackoverflow.com/a/71146522/17112163
  4. https://stackoverflow.com/a/72046825/17112163
  5. https://stackoverflow.com/a/72046933/17112163
Deepthi Tabitha Bennet
  • 798
  • 1
  • 6
  • 14
0

lets assume, the outer loop goes to n and the inner loop goes to the value of the inner loop. (reversal case of your loop). the complete count inner cycles you can calculate with the formula

Sum k=1..n (k) = n * (n+1) / 2 = 1/2 * n^2 + 1/2 n

so you have a time complexity of

O(1/2 * n^2 + 1/2 n) = O(n² + n) = O(n²)

user287107
  • 9,286
  • 1
  • 31
  • 47