Не всегда вложенные циклы увеличивают сложность. Если внутренние циклы влияют на переменную внешнего цикла — сложность может меняться как угодно, а анализировать такие алгоритмы становится сложнее. Изучите пример ниже.

var i = 1;
while (i < n)
{
    var j = i;
    while (j < i + n/10)
        j++;
    i = j + 1;
}

С оценкой сложности в этом примере легко справиться, если заметить, что после окончания внутреннего цикла, i увеличивается ровно на столько, сколько итераций сделал внутренний цикл.

1. Оцените сложность этого кода в зависимости от n 1 балл

Θ(1)

Θ(n)

Θ(n²)

Θ(n³)