Recurrence Equations and Their Closed-Form Solutions
摘要
In so-called “divide and conquer” algorithms one usually ends up with a recurrence relation (i.e., inductive or recursive definition!) that defines the “timing function”, T(n) —such timing indicating worst case upper bound on run time or average run time as the case may be.