Использование частичной подстановки

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

Предположим, вы считаете, что T(n) = O(n log  n), но не уверены в константе  в обозначении O(·). Метод подстановки может использоваться даже без точного значения этой константы.

Сначала записываем T(n) ≤ kn logb n для некоторой константы k и основания b, которые будут определены позднее.

Теперь хотелось бы знать, существуют ли значения k и b, которые будут работать в индукции. Для начала проверим один уровень индукции. 

T(n) ≤ 2T(n/2) + cn ≤ 2k(n/2) logb(n/2) + cn 

Появляется естественная мысль выбрать для логарифма основание b = 2, поскольку мы видим, что это позволит применить упрощение log2(n/2) = (log2 n) − 1. Продолжая с выбранным значением, получаем

T(n) ≤ 2k(n/2) log2(n/2) + cn

= 2k(n/2)[(log2 n) − 1] + cn

= kn[(log2 n) − 1] + cn

= (kn log2 n) − kn + cn.

Наконец, спросим себя: можно ли подобрать значение k, при котором последнее выражение будет ограничиваться kn log2 n? Очевидно, что ответ на этот вопрос положителен; просто нужно выбрать любое значение k, не меньшее c, и мы получаем T(n) ≤ (kn log2 n) − kn + cn ≤ kn log2 n.

Индукция завершена.

Итак, метод подстановки может пригодиться для определения точных значений констант, если у вас уже имеется некоторое представление об общей форме решения.