Временная сложность алгоритма выпуклая оболочка

Question

сложность алгоритма выпуклой оболочки может быть представлена ​​в суммирующей нотации:

1 C(n)=sum(i=1..n-1)sum(j=i+1..n)sum(k=1..n)1 
2 =sum(i=1..n-1)sum(j=i+1..n)n 
3 =nsum(i=1..n-1)sum(j=i+1..n)1 
4 =nsum(i=1..n-1)(n-i) 

И отсюда мой профессор прыгнул прямо:

5 =nsum(i=1..n-1)i 
6 =n*n(n-1)/2 
7 =(n^3-n^2)/2 

Я не» t получить, как он просто избавился от n в строке 4. Я попробовал другой подход и получил совершенно другой ответ:

5 =nsum(i=1..n-1)n - sum(i=1..n-1)i 
6 =nsum(i=1..n-1)n - n(n-1)/2 
7 =n^2sum(i=1..n-1)1 - n(n-1)/2 
8 =n^2(n-1) - n(n-1)/2 
9 =n^3-n^2 - n^2/2 - n/2 

Может ли кто-нибудь объяснить, как мой профессор избавился от n и почему мое решение неверно?

Благодаря

Answer 1

Чтобы увидеть, где ошибка, все, что вам нужно сделать, это выбрать небольшое число для n и посмотреть, как математика работает. Итак, давайте выбираем n=3.

4 =3sum(i=1..2)(3-i) = 3(2+1) = 9 
5 =3sum(i=1..2)i  = 3(1+2) = 9 

Теперь ваш

5 =3sum(i=1..2)3 - sum(i=1..2)i = 3(3+3) - (1+2) = 18-3 = 15 

Проблема заключается в том, что вы не размножались оба термина на n

5 =n(sum(i=1..n-1)n - sum(i=1..n-1)i) 
6 =n((n-1)n - (n-1)n/2) 
7 =n((n-1)n/2) 

Answer 2

Развернуть условия:

nsum(i=1..n-1)(n-i) = (n-1) + (n-2) + ... + (n-(n-1))=1 

Теперь посмотрим на их в обратном порядке е:

1 + ... (n-2) + (n-1) = sum(i=1..n-1)i