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

Corbicula

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. – Kktp

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. – Rufina

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://mcmap.net/q/271061/-what-is-the-worst-case-time-complexity-for-this-algorithm
2. https://mcmap.net/q/269984/-what-is-the-big-o-of-a-nested-loop-where-number-of-iterations-in-the-inner-loop-is-determined-by-the-current-iteration-of-the-outer-loop
3. https://mcmap.net/q/271060/-time-complexity-of-nested-for-loop
4. https://mcmap.net/q/271063/-using-big-o-notation-what-is-the-correct-label-for-this-algorithm
5. https://mcmap.net/q/271064/-nested-for-loop-in-big-oh-complexity

Fantastic

Well explained! – Delainedelainey

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

Sappy

What do you mean by that Outer loop goes to n and inner loop goes to the value of inner loop. I unable to exactly get your point. – Corbicula