Пространственная сложность следующего уравнения

Question

Я не могу понять. пространственная сложность одной из моих программ. его выходит следующим образом, но я не уверен, если это O (N^3), или О (п^4)

1*n + 2*(n-1) + 3*(n-2) + ..+ (n-1) *(2) + n *1 

как я понимаю 1+ 2 + 3 + ....+ n = n*(n-1)/2

и здесь мы имеем два из них , поэтому мне было интересно, будет ли это O (n^4)

Answer 1

Это O (n).

Я вычислил первые пять элементов этой последовательности:

п = 1 -> 1
п = 2 -> 4
п = 3 -> 10
п = 4 -> 20
п = 5 -> 35

The On-Line Encyclopedia of Integer Sequences® (OEIS®) говорит, что это тетраэдрическое (или треугольным пирамидальный) номер: a(n) = C(n+2,3) = n*(n+1)*(n+2)/6.

Конечно, это не доказательство. Вы должны проверить на induction, удовлетворяет ли ваша сумма этому соотношению.