# 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:

A function**Exponential functions:***f*from reals to reals is called an exponential function in*x*if it can be expressed in the form*f*(*x*) =*a*for^{x}*x*,*a*∊ ℜ (the set of real numbers) and*a*> 1. Examples of exponential functions are 2, 1.5^{x}^{x}^{+2}, and 3^{1.5}.^{x}A function**Polynomial functions:***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*for^{b}*x*,*b*∊ ℜ and*b*> 0. A linear function is ...

Get *Introduction to Parallel Computing, Second Edition* now with the O’Reilly learning platform.

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