Using Big O Notation, what is the correct label for this algorithm?

Question

I am curious. What is the correct way to describe this using Big-O Notation?

var prices = [100, 180, 260, 590, 40, 310, 535, 10, 5, 3];
var biggest_profit = 0;
  
for (var i = 0; i < prices.length; i++) {
    var first_price = prices[i];
  
    for (var j = i + 1; j <= prices.length; j++) {
      // do something here
    }
}
  

This is the bit that throws me off:

j = i + 1

Every time we go through i, the j becomes shorter and shorter.

What is the correct name for this pattern in Big O Notation?

Answer 1

You can use Sigma notation to calculate the number of visits of the inner loop ("do something here")

Where (*) follows from a summation rule made famous by the rumour that Gauss once derived it on-the-spot as a young student.

Answer 2

If do something here is an O(1) operation, the whole algorithm is O(N^2).

How to compute? (Thanks to @dfri for error catching)

Outer loop: i: [0->N-1]

Inner loop: j: [i+1->N]

Total= N + (N-1) + (N-2) + (N-3) + ... + 1 = N(N+1)/2 = O(N^2)

Answer 3

To calculate the big O of this algorithm, just imagine a shape: In each iteration of outer for loop, we have a row, made of small squares. Each square is one iteration of inner for loop. So for first iteration of outer for loop, we would have a full line of squares. The second row, will lose one of the squares. And the third row, will lose another one. ... The last row, will just have a single square. Finally we will have this shape:

?????????????_____
????????????_______
???????????________
??????????_________
?????????__________
????????___________
???????____________
??????_____________
?????______________
????_______________
???________________
??_________________
?__________________

This is half of a big square. So its area is: prices.length * (prices.length - 1) * 1/2. And we can remove "-1" because it is little enough. And the result: Prices.length * prices.length * 1/2 The 1/2 isn't important in Big O. So the algorithm has a O(n^2) time complexity.

Answer 4

var prices = [100, 180, 260, 590, 40, 310, 535, 10, 5, 3];
var biggest_profit = 0;

for (var i = 0; i < prices.length; i++) {  // outer loop
    var first_price = prices[i];

    for (var j = i + 1; j <= prices.length; j++) {  // inner loop
        // do something here
    }
}

In the first iteration of the outer loop (i = 0), the inner loop executes N times.

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

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

. . .

In the N - 2th iteration of the outer loop (i = N - 3), the inner loop executes 3 times.

In the N - 1th iteration of the outer loop (i = N - 2), the inner loop executes 2 times.

In the last (Nth) iteration of the outer loop (i = N - 1), the inner loop executes 1 time.

Therefore, the total number of times this code executes is

N + N - 1 + N - 2 + N - 3 + … + 2 + 1

= 1 + 2 + … + N - 3 + N - 2 + N - 1 + N

Substituting this in the Sum of Natural numbers Formula,

= (N)(N + 1) / 2

= ((N^2) + N) / 2

= O(N^2), assuming // do something here executes in constant time O(1).

——————

Also, do take a look at these

1. https://stackoverflow.com/a/71805214/17112163
2. https://stackoverflow.com/a/71146522/17112163
3. https://stackoverflow.com/a/69821878/17112163
4. https://stackoverflow.com/a/71537431/17112163
5. https://stackoverflow.com/a/72046933/17112163