Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |

In 1892, P. Bachmann
invented a notation for characterizing
the asymptotic behavior of functions.
His invention has come to be known as *big oh notation*:

Definition (Big Oh)Consider a functionf(n) which is non-negative for all integers . We say that ``f(n) is big ohg(n),'' which we writef(n)=O(g(n)), if there exists an integer and a constantc>0 such that for all integers , .

- A Simple Example
- Big Oh Fallacies and Pitfalls
- Properties of Big Oh
- About Polynomials
- About Logarithms
- Tight Big Oh Bounds
- More Big Oh Fallacies and Pitfalls
- Conventions for Writing Big Oh Expressions

Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.