Some Technical Details

The ``big'' and ``little'' functions behave almost exactly like their standard real-number counterparts: transitivity, reflexivity, symmetry, and transpose symmetry.

However, one standard property does not hold: trichotomy. There are pairs of functions f(n) and g(n) such that none of f(n) = o(g(n)), tex2html_wrap_inline352 , nor tex2html_wrap_inline414 holds. The book gives an example of tex2html_wrap_inline416 which can't be compared directly to n because it often acts like tex2html_wrap_inline420 .


next up previous
Next: Applying to Algorithms Up: ASYMPTOTIC GROWTH Previous: Big O