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