Какой порядок заполнения матрицы tri angular?

Question

Я заполняю нижнюю матрицу tri angular следующим образом:

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

И я хочу вычислить порядок кода в нотации Big O, но я действительно плохой. Если бы это была обычная матрица, это была бы O (n²), но в этом случае я не уверен, что это O (nlog (n)) или что-то в этом роде.

Answer 1

Обычно (но не всегда) один l oop, вложенный в другой, вызывает O (N²).

Подумайте, внутренний l oop выполняется i раз для каждого значения j. Внешний l oop выполняется size раз.

Это получается 1/2 от N ^ 2, что по-прежнему равно O (N ^ 2)