Тройной вложенный цикл For с двумя независимыми внешними циклами и одним зависимым внутренним циклом

Хорошо, внутренний цикл (цикл с k в качестве итератора) выполняется n-j+1 раз, поскольку он начинается с j и заканчивается на n.

Общее количество шагов , которое выполняет средний цикл for, является суммой шагов на итерацию для j, так что это означает, что общее количество раз, которое мы выполняем тело внутреннего Цикл for:

 n
---
\                  n * (n + 1)
/    n - j + 1  = -------------
---                    2
j=1

, поэтому после одной итерации внешнего цикла (с итератором i) мы имеем n*(n+1)/2 шагов.

Таким образом, в целом наш алгоритм будет выполнять тело внутреннего цикла в общей сложности n * n * (n+1)/2 раз. Поскольку внешний цикл выполняется n раз, а количество шагов в теле этого цикла не не , зависит от значения самого i.

Если мы считаем, что часть num <- j + 1 выполняется в постоянное время (строго говоря, суммирование огромных чисел не может быть выполнено в постоянное время), то это, таким образом, O (n ^{3 )} алгоритм.