Appendix A. Complexity of Functions and Order Analysis
Order analysis and the asymptotic complexity of functions are used extensively in this book to analyze the performance of algorithms.
Complexity of Functions
When analyzing parallel algorithms in this book, we use the following three types of functions:
Exponential functions: A function f from reals to reals is called an exponential function in x if it can be expressed in the form f (x) = ax for x, a ∊ ℜ (the set of real numbers) and a > 1. Examples of exponential functions are 2x, 1.5x +2, and 31.5x.
Polynomial functions: A function f from reals to reals is called a polynomial function of degree b in x if it can be expressed in the form f (x) = xb for x, b ∊ ℜ and b > 0. A linear function is ...