Как найти сложность этого вложенного цикла?

Question

Я немного запутался в этом цикле for.Учитывая число n, мы должны выяснить, сколько раз будет выполняться инструкция.

int j = 0;
for(int p = 0; p < n*n; p++ )
{
    for(int q = 0; q < p; q++ )
    {
        j++;
    }
}

Мой ответ O(n^4).Правильный ли этот ответ?

Answer 1

Вы можете написать соответствующую сигму для сложности времени T(n) = sum_{p = 1}{n^2} sum_{q=1}{p} (1) = sum_{p=1}{n^2} (p) = 1 + 2 + 3 + ... + n^2 = n^2(n^2 + 1)/2 = Theta(n^4). Таким образом, ваш ответ правильный для количества инструкций.