O'Reilly logo

Introduction to Parallel Computing, Second Edition by Vipin Kumar, George Karypis, Anshul Gupta, Ananth Grama

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required