Solved Recurrence - Iterative Substitution (Plug-and-chug) Method
This is an example of the Iterative Substitution Method for solving recurrences. Also known sometimes as backward substitution method or the iterative method.
An example of solving the same recurrence using the Tree method can be found here: https://www.youtube.com/watch?v=sLNPd_nPGIc
Note that there is another method of solving recurrences that is unfortunately called the substitution method by the CLRS Algorithms Book that many R1 instructors use to teach algorithms. This other method is not a little bit like the iterative substitution method used here. It is more accurately called the "guess-and-check" method, since you make a guess about what the runtime is and then prove it by induction.
In a quick survey of the Algorithms textbooks near at hand, CLRS and Klienberg & Tardos call the "guess-and-check" method "substitution" while the books by Neapolitan and by Levin, call what I did the substitution method. Leafing through Rosen it appears to only show the substitution method, but it doesn't name it. Epp's book calls this method the iterated method and does not teach the other method.
The bottom line is that in mathematics it is often the case that a single name is used to refer to multiple things and sometimes a single thing may have multiple names. Even in the same subfield. It's important to remember this and that it's not the name that matters.
Видео Solved Recurrence - Iterative Substitution (Plug-and-chug) Method канала John Bowers
An example of solving the same recurrence using the Tree method can be found here: https://www.youtube.com/watch?v=sLNPd_nPGIc
Note that there is another method of solving recurrences that is unfortunately called the substitution method by the CLRS Algorithms Book that many R1 instructors use to teach algorithms. This other method is not a little bit like the iterative substitution method used here. It is more accurately called the "guess-and-check" method, since you make a guess about what the runtime is and then prove it by induction.
In a quick survey of the Algorithms textbooks near at hand, CLRS and Klienberg & Tardos call the "guess-and-check" method "substitution" while the books by Neapolitan and by Levin, call what I did the substitution method. Leafing through Rosen it appears to only show the substitution method, but it doesn't name it. Epp's book calls this method the iterated method and does not teach the other method.
The bottom line is that in mathematics it is often the case that a single name is used to refer to multiple things and sometimes a single thing may have multiple names. Even in the same subfield. It's important to remember this and that it's not the name that matters.
Видео Solved Recurrence - Iterative Substitution (Plug-and-chug) Method канала John Bowers
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
![Solved Recurrence Tree Method](https://i.ytimg.com/vi/sLNPd_nPGIc/default.jpg)
![Solving Recurrence Relation](https://i.ytimg.com/vi/wXaEnbZkGY0/default.jpg)
![Method of Iteration - Recursive Relations](https://i.ytimg.com/vi/TyBujmbbpQM/default.jpg)
![2.1.1 Recurrence Relation (T(n)= T(n-1) + 1) #1](https://i.ytimg.com/vi/4V30R3I1vLI/default.jpg)
![2.1.2 Recurrence Relation (T(n)= T(n-1) + n) #2](https://i.ytimg.com/vi/IawM82BQ4II/default.jpg)
![How to Solve a Second Order Linear Homogeneous Recurrence Relation(Distinct Real Roots Case)](https://i.ytimg.com/vi/d5jTxBNK6OU/default.jpg)
![Iteration Method To Solve Recurrence Relation (Data Structure and Algorithms)](https://i.ytimg.com/vi/ZUE8Qi4sRBo/default.jpg)
![Fixed Point Iteration Method - KTU (2015 Syllabus) - MA202 - Module 5](https://i.ytimg.com/vi/mGYpVc1AZOM/default.jpg)
![Solving Recurrences](https://i.ytimg.com/vi/KGu6_fiN9ro/default.jpg)
![How To Solve Recurrence Relations](https://i.ytimg.com/vi/honkPbYEc7Q/default.jpg)
![Master theorem | Solving Recurrences | Data Structure & Algorithm | GATE APPLIED COURSE](https://i.ytimg.com/vi/2y0HQGd1-nA/default.jpg)
![L-2.6: Recurrence Relation [ T(n)= 8T(n/2) + n^2 ] | Master Theorem | Example#1 | Algorithm](https://i.ytimg.com/vi/FBKjvXGGCJM/default.jpg)
![T (n) = 3T(n/3) + n^3](https://i.ytimg.com/vi/lkQWde4ZCC0/default.jpg)
![Recurrence Relation Proof By Induction](https://i.ytimg.com/vi/t_3ACuzEe_8/default.jpg)
![Solving Linear Recurrence Relations 1](https://i.ytimg.com/vi/aHw7hAAjbD0/default.jpg)
![2.1.4 Recurrence Relation T(n)=2 T(n-1)+1 #4](https://i.ytimg.com/vi/JvcqtZk2mng/default.jpg)
![Recursion Tree Method](https://i.ytimg.com/vi/lBFiDGkR9-M/default.jpg)
![Recurrence Relations: Substitution Method](https://i.ytimg.com/vi/7lq-rBdM62o/default.jpg)
![Substitution method | Solving Recurrences | Data Structure & Algorithm | Appliedroots](https://i.ytimg.com/vi/LC96q_6r3BQ/default.jpg)
![Master Method ( incl. Step-By-Step Guide and Examples ) - Analysis](https://i.ytimg.com/vi/6CX7s7JnXs0/default.jpg)