A.1 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 a polynomial function of degree one and a quadratic function is a polynomial function of degree two. Examples of polynomial functions are 2, 5x, and 5.5x2.3. A function f that is a sum of two polynomial functions g and h is also a polynomial function whose degree is equal to the maximum of the degrees of g and h. For example, 2x + x2 is a polynomial function of degree two.
Logarithmic functions:
A function f from reals to reals that can be expressed in the form f (x) = logb x for b and b > 1 is logarithmic in x. In this expression, b is called the base of the logarithm. Examples of logarithmic functions are log1.5 x and log2 x. Unless stated otherwise, all logarithms in this book are of base two. We use log x to denote log2x, and log2 x to denote (log2 x)2.
Most functions in this book can be expressed as sums of two or more functions. A function f is said to dominate a function g if f (x) grows at a faster rate than g(x). Thus, function f dominates function g if and only if f (x)/g(x) is a monotonically increasing function in x. In other words, f dominates g if and only if for any constant c > 0, there exists a value x0 such that f (x) > cg(x) for x > x0. An exponential function dominates a polynomial function and a polynomial function dominates a logarithmic function. The relation dominates is transitive. If function f dominates function g, and function g dominates function h, then function f also dominates function h. Thus, an exponential function also dominates a logarithmic function.
 |
