Для решения основной теоремы рекуррентного соотношения необходимо выразить время выполнения алгоритма как рекурсивную функцию от размера входных данных в виде: T(n) = aT(n/b) + f(n), где: 23

• n — объём входных данных; 3
• a — количество подзадач в рекурсии; 3
• n/b — размер каждой подзадачи. 3 Предполагается, что все подзадачи имеют одинаковый размер; 3
• f(n) — оценка выполненной работы вне рекурсивных вызовов. 3 Также она включает в себя вычислительную стоимость деления на подзадачи и объединения решений этих подзадач. 3

Пример решения для сортировки слиянием: уравнение принимает вид: T(n) = aT(n/b) + f(n) = 2T(n/2) + O(n). 5 Здесь: 5

• a = 2 (на каждом шаге задача делится на две подзадачи); 5
• n/b = n/2 (размер каждой подзадачи — половина исходной); 5
• f(n) = затраченное время на деление задачи на подзадачи и их последующее объединение; 5
• T(n/2) = O(n log n). 5

В конечном итоге T(n) = 2T(n log n) + O(n) ≈ O(n log n). 5

Код сортировки слиянием можно найти, например, на сайте pythonist.ru в статье о реализации этого алгоритма на Python. 1