Recurrence Formulas
represent time for recursive expressions
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)
