Вычислить функцию

[iskander9908]

Зашёл в тупик решая задачу из книги по алгоритмам. Нужно вычислить функцию через переменную и найти её ассимпотическую сложность:

Pestiferous (n)
       r = 0;
       for i = 1 to n do
           for j = 1 to i do
               for k = j to i + j do
                   for l = 1 to i + j - k do
                           r = r + 1;
       return (r) 

Я пробывал вычислить через суммы $\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{i}\sum\limits_{k = j}^{i + j}\sum\limits_{l = 1}^{i + j - k} 1$ и получил $r = \frac{n(n + 1)(n + 2)(n + 3)}{24}$, но ответ не прошёл проверку компьютером.

[Dedekind]

iskander9908
А переменные в Ваших циклах принимают значения на верхнем пределе? То есть, например, переменная $i$ должна пробегать значения $1, 2, ..., n$ или $1, 2, ..., n-1$?

[iskander9908]

Dedekind в сообщении #1628877 писал(а):

iskander9908
А переменные в Ваших циклах принимают значения на верхнем пределе? То есть, например, переменная $i$ должна пробегать значения $1, 2, ..., n$ или $1, 2, ..., n-1$?

От $1$ до $n$.

-- 09.02.2024, 01:00 --

Допустил нелепую ошибку в вычислении сум. Вот решение:
$\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{i}\sum\limits_{k = j}^{i + j}\sum\limits_{l = 1}^{i + j - k} 1 = $\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{i}\sum\limits_{k = j}^{i + j} (i + j - k) = $\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{i} (( i + j )(i + 1) - (i + 1)j - \frac{i(i + 1)}{2}) = $\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{i}\frac{i^2 + i}{2} = $\sum\limits_{i = 1}^{n} \frac{i^3 + i^2}{2} = \frac{n^2(n + 1)^2}{8} + \frac{n(n + 1)(2n + 1)}{12} = \frac{n(n + 1)(n + 2)(3n + 1)}{24} = O(n^4)$

[Dedekind]

iskander9908
Неправильно посчитана сумма. Последний множитель должен быть $3n+1$.

-- 08.02.2024, 21:07 --

А, вижу, Вы уже разобрались:)