 |  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
Growth of Functions
Glossary
| asymptotically positive | a function that is positive for all sufficiently large n
| | | | | asymptotically tight bound | For all n ≥ n0, the function f(n) is equal to g(n) to within a constant factor. We say that g(n) is an asymptotically tight bound for f(n).
(See page 43)
| | | | | asymptotically smaller | We say that f(n) is asymptotically smaller than g(n) if f(n) = o(g(n)).
(See page 49)
| | | | | asymptotically larger | f(n) is asymptotically larger than g(n) if f(n) = ω(g(n)).
(See page 49)
| | | | | monotonically increasing | A function f(n) is monotonically increasing if m ≤ n implies
f(m) ≤ f(n).
(See page 51)
| | | | | monotonically decreasing | A function f(n) is monotonically decreasing if m ≤ n implies
f(m) ≥ f(n).
(See page 51)
| | | | | strictly increasing | A function f(n) is strictly increasing if m < n implies f(m) < f(n).
(See page 51)
| | | | | strictly decreasing | A function f(n) is strictly decreasing if m < n implies f(m) > f(n).
(See page 51)
| | | | | Fibonacci numbers | The Fibonacci numbers are defined by the following recurrence:
F0 = 0 ,
F1 = 1 ,
Fi = Fi-1 + Fi-2 for i ≥ 2.Thus, each Finonacci number is the sum of the two previous ones, yielding the sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... .
(See page 56)
| | | | | polynomially bounded | A function f(n) is polynomially bounded if f(n) = O(nk) for some constant k.
(See page 52)
| | | | | polylogarithmically bounded | A function f(n) is polylogarithmically bounded if f(n) = O(lgkn) for some constant k.
(See page 54)
| | | | | remainder (or residue) | For any integer a and any positive integer n, the value a mod n is the remainder (or residue) of the quotient a / n: a mod n = a - ⌊a/n⌋n.
(See page 51)
|
|
2002 McGraw-Hill Higher Education