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) = ax for x, a ∊ ℜ (the set of real numbers) and a > 1. Examples of exponential functions are 2x, 1.5x +2, and 31.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) = xb for x, b ∊ ℜ and b > 0. A linear function is ...

Get Introduction to Parallel Computing, Second Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.