Некоторые методы анализа рекурсивных алгоритмов:

• Метод подстановки. 13 Используется для предположения формы решения и доказательства по индукции. 1
• Метод дерева рекурсии. 1 Рекурсивные вызовы визуализируются в виде дерева, где каждый узел представляет вызов функции. 1
• Метод мастера. 1 Шаблон для анализа рекуррентных уравнений вида: T(n) = a * T(n / b) + f(n). 1
• Метод рекуррентных соотношений. 4 Идея метода состоит в построении и решении рекуррентного соотношения, которому удовлетворяет функция сложности алгоритма. 4 Найденное решение позволяет получить О-оценку для функции сложности. 4
• Теоретико-графовый метод исследования дерева рекурсии. 4 Применяется, когда не удаётся получить рекуррентное соотношение для функции временной сложности. 4