Большая сложность для вложенного цикла

Question

Я должен найти сложность Big O для этого цикла:

for(i=0; i<n; i++)
    for(j=0; j<n-i; j++)
        print(i)

Я думаю, что это O (n ^ 2), но я не совсем уверен. Кто-нибудь может мне помочь?

Answer 1

Вы правы, сложность O(n^2).

• Первый цикл (for(i=0; i<n; i++)) довольно прост. Это O(n).

• Второй цикл (for(j=0; j<n-i; j++)) сложнее: он (теоретически) O(n - i).

Когда вы объедините эти два, вы получите:

O = n^2 - i*n

Поскольку нотация Bit O принимает только самый большой коэффициент, вы просто удаляете - i*n и в итоге получаете:

O(n^2)