Which is the order of filling a triangular matrix?

Question

I'm filling a lower triangular matrix like this:

for (i = 0; i < size; i++) {
    for (j = 0; j <= i; j++)
        l[i][j] = j + 1;
}

And I want to calculate the order of the code in Big O notation but I'm really bad. If it was a regular matrix it would be O(n²) but in this case I'm not sure if it's O(nlog(n)) or something like that.

Since a triangular matrix, it would have (n²/2) entries which is still O(n²) — Abhay Aravinda, May 02 '20 at 11:13
So it doesn't matter if I also fill the upper triangle with zeros? It will have the same order? Thank you! :) — Migue Feixas, May 02 '20 at 11:17
It will have the same order. But it doesn't mean they will take the same time to execute. No point filling zeroes if it is unwanted — Abhay Aravinda, May 02 '20 at 11:18
Does this answer your question? [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — Paul Hankin, May 02 '20 at 11:43

score 1 · Accepted Answer · answered May 02 '20 at 11:23

1

Typically (but not always) one loop nested in another will cause O(N²).

Think about it, the inner loop is executed i times, for each value of j. The outer loop is executed size times.

This comes out to be 1/2 of N^2, which is still O(N^2)

answered May 02 '20 at 11:23

Lakshitha Wisumperuma

1,574
1
10
17

Which is the order of filling a triangular matrix?

1 Answers1