Introduction to Parallel Computing, Second Edition

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:

1. 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.5x.

2. 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 ...