Не получается решить задачу на анализ алгоритма(задача из книги Стивена Скиена "Алгоритмы. Руководство по разработке.")

O(n^3)

Функция вычисляет количество итераций, которое происходит во вложенных циклах. Внутренний цикл k работает O(n - i - j + 1) раз на каждой итерации внешнего цикла j, а внешний цикл j работает O(n - i) раз на каждой итерации внешнего цикла i. Следовательно, время работы данной функции в наихудшем случае составляет O(n^3).

Для нахождения значения, которое вернет функция, можно вычислить количество итераций, которое будет выполнено в циклах. Рассмотрим сначала внутренний цикл k. Поскольку k должен быть не меньше, чем i+j-1 и не больше, чем n, то количество итераций в цикле k на i-ой итерации внешнего цикла j будет равно n - (i + j - 1) + 1, или n - i - j + 2. Тогда количество итераций внутреннего цикла k при фиксированных значениях i и j будет равно сумме от (n - i - j + 2) до n, или (n - i - j + 2) * (n - i - j + 3) / 2. Заметим, что i+1 должно быть меньше, чем n, поэтому j не может начинаться с n-1. Аналогично, i не может начинаться с n-2. Используя эти ограничения, мы можем найти сумму всех итераций в циклах и получить ответ:

def F(n):
r = 0
for i in range(1, n - 1):
for j in range(i + 1, n):
r += (n - i - j + 2) * (n - i - j + 3) // 2
return r

Например, F(4) вернет 16, потому что есть 16 итераций во внутренних циклах:

(i=1,j=2,k=3),(i=1,j=2,k=4),(i=1,j=3,k=4),(i=2,j=3,k=4)
(i=2,j=1,k=2),(i=2,j=1,k=3),(i=3,j=1,k=2),(i=3,j=1,k=3)
(i=2,j=4,k=4),(i=3,j=4,k=4),(i=1,j=4,k=4),(i=1,j=3,k=3)
(i=1,j=2,k=2),(i=2,j=3,k=3),(i=2,j=4,k=3),(i=3,j=4,k=3)

Общее количество итераций равно 16.