Appendix C. Algorithmic Complexity

Often, in computer science and related disciplines, it is useful to express the algorithmic complexity—or scalability—of algorithms as a meaningful value (as opposed to less descriptive terms, such as gross). Various methods exist for representing scalability. One common technique is to study the asymptotic behavior of the algorithm. This is the behavior of the algorithm as its inputs grow exceedingly large and approach infinity. Asymptotic behavior shows how well an algorithm scales as its input grows larger and larger. Studying an algorithm's scalability—how it performs as the size of its input increases—enables us to model the algorithm against a benchmark and better understand its behavior.


An algorithm ...

Get Linux Kernel Development, Second Edition now with O’Reilly online learning.

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