## An Introduction to Asymptotic Behavior

By Herbert J. Bernstein

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 n0 and constant c > 0 such that for all integer nn0, f( n ) ≤ cg( n ).

• "Ω": f( n ) = Ω( g( n ) ) iff there exists integer n0 and constant c > 0 such that for all integer nn0, 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