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?

Possible duplicate of [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?](http://stackoverflow.com/questions/362059/what-is-the-big-o-of-a-nested-loop-where-number-of-iterations-in-the-inner-loop) — Paul Hankin, Aug 07 '16 at 01:10

Humam Helfawi · Answer 1 · 2016-08-06T18:50:03.287

5

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)

edited Aug 06 '16 at 18:50

answered Aug 06 '16 at 18:00

Humam Helfawi

19,566
15
85
160

How do you derive the Total from the outer and inner loop running times? – stackoverflowuser2010 Aug 06 '16 at 18:10
To be picky, the outer loop runs from `i+1` to `N-1` (not `N`), yielding a total inner loop visit count of `N(N+1)/2` (the end result in terms of asymptotic analysis is naturally the same, though). @stackoverflowuser2010: I've added an alternative answer for those possibly interested in more details of the loop count calculation. – dfrib Aug 06 '16 at 18:41
1

@dfri Thanks for notifying – Humam Helfawi Aug 06 '16 at 18:43

score 5 · Accepted Answer · answered Aug 06 '16 at 18:38

5

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.

answered Aug 06 '16 at 18:38

dfrib

70,367
12
127
192

score 2 · Answer 3 · edited Aug 08 '16 at 00:42

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.

Deepthi Tabitha Bennet · Answer 4 · 2022-04-28T16:06:50.497

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

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

4 Answers4

Linked