Понадобятся две формулы:

1) для суммы арифметической прогрессии S = a₁ + a₂ + ... + a_k = (a₁+a_k)[$183$]k/2
2) для суммы квадратов натуральных чисел от 1 до k: 1² + 2² + 3² +...+k² = k[$183$](k+1)[$183$](2[$183$]k+1)/6

Вторая формула не очень известна. При желании ее можно доказать методом математической индукции.

Обратим внимание, что численно r будет равно количеству раз, которое выполняется k в программе. Значит, ищем сколько раз выполнится k в программе.

Смотрим на внутренний цикл (с к). При фиксированном j он выполняется ровно j раз. То есть нашли, сколько раз выполняется цикл k при фиксированном j.

Но ведь j меняется! Поэтому теперь смотрим на цикл с j. Первое значение j равно (i+1), потом (i+2) и т.д. до n. Значит, внутренний цикл k выполнится сначала (i+1) раз, потом (i+2) раз и т.д. до n раз. А в сумме это равно:

S = (i+1) + (i+2) + (i+3) + ... n, т.е. сумма арифметической прогрессии от (i+1) до n. Всего членов (n - (i+1) + 1) = (n-i). Значит, используя вышеуказанную формулу, получаем:

S = { (i+1) + n}[$183$](n-i)/2 = (n+i+1)[$183$](n-i)/2 = (n² - i² + n - i)/2 = (n² + n)/2 - (i² + i)/2, т.е. сгруппировал отдельно члены, зависящие и не зависящие от i.

Таким образом, нашли, сколько раз выполняется внутренний цикл k при фиксированном i. Поскольку i тоже меняется, то теперь смотрим на цикл с i.

Значения i меняются от 1 до n-1. Значит, ищем сумму с этими пределами:

[$931$]{ (n² + n)/2 - (i² + i)/2} = [$931$](n² + n)/2 - 1/2[$183$][$931$] i² - 1/2[$183$][$931$] i =
=(n-1)[$183$](n² + n)/2 - 1/2[$183$]1/6[$183$](n-1)[$183$]n[$183$](2[$183$]n-1) - 1/2[$183$]n[$183$](n-1)/2 =
(то есть использовали обе вышеуказанные формулы и учли, что k=n-1)
= (n-1)/12[$183$]{ 6[$183$]n² + 6[$183$]n - 2[$183$]n² + n - 3[$183$]n}= (n-1)/12[$183$]{ 4[$183$]n² + 4[$183$]n}=
= (n-1)/12[$183$]4[$183$]n[$183$](n+1) = n[$183$](n² - 1)/3 = n³/3 - n/3

ОТВЕТ: n³/3 - n/3. Получается О(n³).