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) = a^{x} for x, a (the set of real numbers) and a > 1. Examples of exponential functions are 2^{x}, 1.5^{x} ^{+2}, and 3^{1.5}^{x}.
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) = x^{b} 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.5x^{2.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 + x^{2} 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) = log_{b} 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 log_{1}._{5} x and log_{2} x. Unless stated otherwise, all logarithms in this book are of base two. We use log x to denote log_{2}x, and log^{2} x to denote (log_{2} 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 x_{0} such that f (x) > cg(x) for x > x_{0}. 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.
