Вычислить временную сложность алгоритма в большой тэте

Question

s = 0 

for i in range(N) :
    for j in range(i):
        s += j

Какова временная сложность этого алгоритма в больших тета-нотациях?

Answer 1

Вы можете рассмотреть это для различных значений i:

• i=1 => количество прогонов s+=j = 1
• i=2 => числоколичество прогонов s+=j = 2

• i=3 => количество прогонов s+=j = 3

  ...

• 'i = N' => количество прогонов s+=j = N

Таким образом, в сумме мы имеем: 1 + 2 + ... N = N(N+1) / 2

Следовательно, время работыбудет: θ (N ² )