Какова сложность Big O когда-либо уменьшающегося диапазона на контуре?

Question

Я получил 2 вложенных цикла, я вычисляю новое значение для nrResults при каждом выполнении внутреннего цикла for (который будет повторять цикл nnrResults - 2 раза).

Сложность времени должна быть порядка O(n), поскольку nrResults зависит от значения n.
Но nrResults уменьшается в каждом цикле внешнего цикла for (т.е. firstNext * j растет с каждой итерацией)

Является ли временная сложность внутреннего цикла foor по-прежнему O(n), хотя nrResults будет продолжать уменьшаться на протяжении всего выполнения?

Заранее спасибо.

for(int j = 1; j < B; j++)                      // General case
        {
            nrResults = n - (firstNext * j);
            result = codedInput[0] + results[minI = minIndex(results, 0 + firstNext, nrResults + firstNext)];

            for(int i = 1; i < nrResults; i++)
            {
                if( (i + firstNext) > minI)
                    results[i] = codedInput[i] + results[minI = minIndex(results, i + firstNext, nrResults + firstNext)];
                else
                    results[i] = codedInput[i] + results[minI];

                if(results[i] < result)
                    result = results[i];
            }
        }

Answer 1

В этом случае у вас есть один цикл i: = 0..n и внутренний цикл j: = 0..i-2.Это так?

Сложность для внутреннего цикла будет O ((n-1) / 2), что является средним значением.Сложность для внешнего for - O (n).

Все, что вам нужно сделать, это умножить O ((n) * (n / 2)), то есть O (n² / 2).

В случае, если внутренний для итераций отличается, вы должны пересчитать его.