Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

An Asymptotic Upper Bound-Big Oh

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 function f(n) which is non-negative for all integers tex2html_wrap_inline57996. We say that ``f(n) is big oh g(n),'' which we write f(n)=O(g(n)), if there exists an integer tex2html_wrap_inline57984 and a constant c>0 such that for all integers tex2html_wrap_inline58018, tex2html_wrap_inline58020.



next up previous contents index

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