Временная сложность двойного цикла, когда i является внешним циклом, а внутренний цикл начинается с j = i + 1

Question

Я пытаюсь получить больше ясности относительно сложности алгоритма, который я написал ниже:

left = 1
right = 1

for i=0; i < array.len; i ++:
        j = i+1
        for j; j < array.len; j++:
             right *= array[j]
        tmp[i] = array[idx]
        left *= array[idx]
        right = 1
return tmp

Если мы определим размер массива равным n, то O (n) для внешнего цикла, но внутреннийцикл на самом деле не повторяется n-1 раз все время, только в первый раз, когда i = 0.

Итак, какова будет сложность?O (n) для внешнего цикла и O (nj) для внутреннего цикла?Так может быть O (n (nj))?Что в итоге становится O (n ^ 2)?

Помогите пожалуйста.

Answer 1

да, O (n ^ 2) - сложность времени.Первый цикл выполняется n раз.второй цикл выполняется n раз для каждой итерации первого цикла.n * n = n ^ 2