Большая сложность O трех вложенных циклов с последним l oop в операторе if

Question

Предположим, у нас есть следующий блок кода:

sum = 0;
for(i = 0; i < n; i++)
    for(j = 0; j < n; j++)
        if(i == j)
            for(k = 0; k < n; k++)
                sum++;

В книге, которую я читаю, указано, что сложность O (n ^ 2), то есть (n ^ 2), если быть точным , но я не уверен почему. При попытке вычислить его сам я получаю O (n ^ 3):

1. Наружный l oop сложность O (n)
2. На втором l oop сложность добирается до O (nˆ2), следуя правилу вложенных циклов
3. Оператор if будет истинным n раз, поэтому к третьему l oop сложность будет O (n * nˆ2)
4. Оператор sum ++ занимает постоянное время, поэтому сложность остается на уровне O (nˆ3)

Это моя логика c, но, похоже, она ошибочна. В чем причина сложности O (n ^ 2) здесь?

Answer 1

Второй l oop проходит n шагов. Каждый шаг занимает только постоянное время (вычисление оператора if), за исключением одного шага. i -й шаг занимает O(n), потому что третий l oop выполнен. Таким образом, второй l oop занимает всего 2n = O(n). Таким образом, в общей сложности вы получите O(n^2).