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: • Solved Recurrence Tree...
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.
13 окт 2016
