 |  Introduction to Algorithms, 2/e Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
Recurrences
Glossary
| recurrence | an equation or inequality that describes a function in terms of its value on smaller inputs.
(See page 62)
| | | | | substitution method | A method for solving recurrences - that is, for obtaining asymptotic "Θ" or "O" bounds on the solution. In the substitution method, we guess a bound and then use mathematical induction to prove our guess correct.
(See page 62)
| | | | | recursion-tree method | A method for solving recurrences - that is, for obtaining asymptotic "Θ" or "O" bounds on the solution. The recursion-tree method converts the recurrence into a tree whose nodes represent the costs incurred at various levels of the recursion; we use techniques for bounding summations to solve the recurrence.
(See page 62)
| | | | | master method | A method for solving recurrences - that is, for obtaining asymptotic "Θ" or "O" bounds on the solution. The master method provides bounds for recurrences of the form T(n) = aT(n / b) + f(n), where a ≥ 1, b > 1, and f(n) is a given function; it requires memorization of three cases, but once you do that, determining asymptotic bounds for many simple recurrences is easy.
(See page 62)
| | | | | recursion tree | In a recursion tree, each node represents the cost of a single subproblem somewhere in the set of recursive function invocations.
(See page 67)
| | | | | Monge array | An m x n array A of real numbers is a Monge array if for all i, j, k, and l such that 1 ≤ i < k ≤ m and 1 ≤ j < l ≤ n, we have A[i, j] + A[k, l] ≤ A[i, l] + A[k, j].
(See page 88)
|
|
2002 McGraw-Hill Higher Education