Рассмотрим это рекуррентное соотношение: x(n) = x(n/2) + n, для n > 1 и x(1) = 0.
Теперь здесь метод обратной замены будет бороться за значения n, а не степени 2, поэтому лучше здесь известно использование правила гладкости для решения этого типа вопросов, и когда мы используем правило гладкости, где мы будем решать для n = 2^k (для n = значения степеней 2), у нас будет решение x(n) = 2n - 1.
Однако, если мы используем метод обратной подстановки, это рекуррентное отношение будет иметь решение!
x(n) = x(n/2) + n = x(n/4) + n/2 + n = x(n/8) + n/4 + n/2 + n = x(n/16) + n/8 + n/4 + n/2 + n = ....
, где шаблон равен
x(n) = x(n/i) + n/(i/2) + n/(i/4) + n/(i/8) + n/(i/16) + ...
, который остановится, когда n = 1 (т.е. когда i = n) и в этом случае
x(n) = x(n/n) + n/(n/2) + n/(n/4) + n/(n/8) + n/(n/16) + ... = 1 + 2 + 4 + 8 + 16 + ... = 2^(n+1) - 1
, что является двумя разными ответами!
Так что, пожалуйста, я так запутался здесь, потому что в учебнике (Введение в анализ и разработку алгоритмов Ананы Левитин) это упоминание, что мы должны использовать здесь правило гладкости, но, как вы можете видеть, я решил это точно методом обратной подстановки, где метод должен был бороться здесь, но ничего не случилось!