Recurrence Formulas
represent time for
recursive expressions
fac(n)
= n == 0 ? 1 : n*fac(n-1)
T(0)
=> 1;
T(n)
=> T(n-1) + 3;
recurrence
for counting
steps as a function of
input n
By McCarthyÕs Transformation, recurrence formulas can be used for arbitrary imperative computations as well.
Cost
of computing fac(n-1)
Incremental
cost (*, -, == comparison)