Количество повторений вложенного цикла зависит от параметра внешнего цикла

Введем следующие обозначения:

k - количество повторений внешнего цикла. В примере k=n.

f(k) – функция зависимости количества повторений вложенного цикла от числа повторений внешнего цикла. В примере f(1)=1, f(2)=2, …, f(n)=n.

T⁽¹⁾, T⁽²⁾ - временная сложность тела цикла 1-го (верхнего) уровня и 2-го уровня (вложенного цикла) соответственно. В примере T⁽²⁾ = 2.

a⁽¹⁾ - временная сложность операторов, предшествующих вложенному оператору цикла, в теле цикла верхнего уровня. В примере a⁽¹⁾ = 1.

b⁽¹⁾ - временная сложность операторов, следующих после вложенного оператора цикла, в теле цикла верхнего уровня. В примере b⁽¹⁾ = 2.

T – временная сложность всего алгоритма.

a – временная сложность операторов, предшествующих циклу, в основном алгоритме. В примере a=1.

b – временная сложность операторов, следующих после цикла в основном алгоритме. В примере b=1.

T = a+b+k∙ (a⁽¹⁾ +b⁽¹⁾) + T⁽²⁾∙

11) Оценка сложности рекурсивных алгоритмов: рекурсия с 1 и многими рекурсивными вызовами, случай косвенной рекурсии.

Под рекурсией понимается метод определения функции через её предыдущие и ранее определенные значения, а так же способ организации вычислений, при котором функция вызывает сама себя с другим аргументом.

При прямой рекурсии процедура содержит вызов себя в собственном теле, например: