By Herbert J. Bernstein

© Copyright, Herbert J. Bernstein, 2003

This is a brief introduction to the asymptotic behavior of functions of use in analysis of algorithms. For a full discussion, see Bruno R. Preiss, "Data Structures and Algorithms with Object-Oriented Design Patterns in Java", http://www.brpreiss.com/books/opus5/html/page58.html.

- Asymptote -- a curve that is approached as some parameter (usually
problem size), goes to infinity.
- Big "O":
*f*(*n*) =*O*(*g*(*n*) ) iff there exists integer*n*_{0}and constant*c*> 0 such that for all integer*n*≥*n*_{0},*f*(*n*) ≤*cg*(*n*). - "Ω":
*f*(*n*) =*Ω*(*g*(*n*) ) iff there exists integer*n*_{0}and constant*c*> 0 such that for all integer*n*≥*n*_{0},*f*(*n*) ≥*cg*(*n*). - "Θ":
*f*(*n*) =*Θ*(*g*(*n*) ) iff*f*(*n*) =*O*(*g*(*n*) ) and*f*(*n*) =*Ω*(*g*(*n*) ) - Little "o":
*f*(*n*) =*o*(*g*(*n*) ) iff*f*(*n*) =*O*(*g*(*n*) ) and*f*(*n*) is not*Ω*(*g*(*n*) ) *log*grows more slowly than any power > 0.- Any non-negative power grows more slowly than any higher power.
- Any polynomial is dominated by its term of highest degree.
- An exponential grows faster than any power.

Last Updated on 23 September 2003

By Herbert J. Bernstein

Email: *yaya@bernstein-plus-sons.com** *