Big O Обозначение для с n ^ 3 Вложенные для циклов

Question

Учитывая следующий код:

for ( int j = 0; j < 2n; j++)
{
    for ( int k = 0; k < n^3; k += 3)
        sum++;
}

Является ли сложность O (n ^ 2)? Влияет ли n ^ 3 в цикле for на нотацию для LARGE N?

Answer 1

O (N ^ 4)

сумма ++ называется 2 * n * (n ^ 3) / 3 раза.

Answer 2

если вы рассматриваете только внутренний цикл, он выполняется N ^ 3 раза

внешний цикл заставляет внутренний цикл выполняться N раз, поэтому общая сложность = N * N ^ 3 = N ^ 4

Answer 3

Внешний цикл имеет O (2n) операций.Внутренний цикл имеет O (n ^ 3) операций.Вместе программа имеет O (n) * O (n ^ 3) = O (N ^ 4).

Answer 4

Точное количество итераций и порядок сложности роста можно вывести формально: