Анализ сложности, который делает каждый элемент в массиве равным наибольшему элементу

Question

Какова сложность данного кода в зависимости от размера задачи n? Показать детали вашего анализа.

for (int i = 0; i < 2*n; i++)
{
    if (i == n)
    {
        for (int j = 0; j < i; j++)
            for (int k = 0; k < i; k++)
                O(1)
    }
    else
    {
        for (int j = 0; j < i; j++)
            O(1)
    }
}

Мои мысли пока:

Операторы if не всегда могут быть истинными (может быть log n). Вложенные внутренние для циклов - n ^ 2.

Буду признателен за любую помощь в том, как ее решить или как ее решить.

Спасибо.

Answer 1

Без if(i == n) {} число операций:

1 + 2 + 3 + 4 + 5 + ... + n*2

= (2n * (2n-1))/2

Но при i==n количество операций не i, как у остальных, а i². Таким образом, окончательное число операций:

((2n * (2n-1))/2) - n + n²

Обозначение Big O вышеупомянутого O (n²)