Экспресс Время работы в Big Theta Notation?

Question

Для этого псевдокода, как я могу выразить время выполнения в обозначении in в терминах n?

s = 0 
    for i = 0 to n: 
    for j = 0 to i: 
     s = (s + i)*j 
print s 

Answer 1

Назначение s = (s + i) * j имеет постоянную временную сложность Θ (1). Для каждого i внутренний цикл выполняется в точности i раз, тогда как i выполняется итерацией от 0 до n. Таким образом, выполняется тело вашего цикла (например, назначение) 1 + 2 + 3 + ... + (n + 1) = (n + 1) (n + 2)/2 = Θ (n^2) ,

Поскольку тело цикла равно Θ (1), вы получаете Θ (n^2) для всей программы, отмечая, что первая и последняя строки являются просто Θ (1), поэтому вы можете их игнорировать.