Substitution method

[sasha1024]

• метод підстановок,
• метод підстановки?

[pasichna]

Множинна форма „метод підстановок“ правильна, бо при розв'язуванні цим методом здійснюється не одна підстановка, а цілий ряд послідовно крок за кроком, поки не дійдемо до базового значення T(1), хоча починаємо переважно від T(n). На кожному кроці підстановки зменшується на одиницю (чи на більше) найбільше значення змінної n у правій частині рекурентного співвідношення (n -> n-1-> n-2-> n-3->…->1).

[sasha1024]

Я теж так думав (і навіть звучить так краще).
Але отут (Ваше посилання) — «метод підстановки».
Тому й вирішив перепитати (дякую).

[pasichna]

Мусив заглянути в англійський оригінал тої книжки. Автори по іншому подають цей метод, ніж я звик. В їхньому аналізі використовується таки дійсно одна підстановка, бо вони припускають представлення розв'язку у вигляді загальної формули з кількома параметрами, яку й підставляють у рекурентне співвідношеня для відшукання параметрів.

Хоча у книжці Boxer, Laurence, and Russ Miller. Algorithms Sequential and Parallel : A Unified Approach, Course Technology, 2005 той метод інакше описаний - саме так я писав у попередній відповіді.
Треба дотримуватися тлумачення авторів.