O(n) and time complexity function of the given code

Question

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

Answer 1

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

Answer 2

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²)