Какова временная сложность этих двух вложенных циклов?

Question

Я обнаружил, что временная сложность этого кода равна O (N). Это правильно?

for(i=n;i>=1;i--) { 
    for(j=n-i; j>=1; j--) { 
    x++; 
    } 
} 

Answer 1

Да, это O (п).

Наружный цикл будет выполнен n раз. Внутренний цикл, в среднем, будет выполнен n/2 раз. Умножьте сложность внутреннего контура и внешнего контура, чтобы получить O(n * n/2), который равен O (n).