flâneur

Using the substitution and master methods

cs.cornell.edu · 2,290 words · saved by 1 readers

The substitution method is a condensed way of proving an asymptotic bound on a recurrence by induction. In the substitution method, instead of trying to find an exact closed-form solution, we only try to find a closed-form bound on the recurrence. This is often much easier than finding a full closed-form solution, as there is much greater leeway in dealing with constants.

Using the substitution and master methods Using the substituion and master methods Using the substituion method The substitution method is a condensed way of proving an asymptotic bound on a recurrence by induction. In the substitution method, instead of trying to find an exact closed-form solution, we only try to find a closed-form bound on the recurrence. This is often much easier than finding a full closed-form solution, as there is much greater leeway in dealing with constants. The substitution method is a powerful approach that is able to prove upper bounds for almost all recurrences. How

related reading