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

Conventions for Writing Big Oh Expressions

Certain conventions have evolved which concern how big oh expressions are normally written:

Of course, in order for a particular big oh expression to be the most useful, we prefer to find a tight asymptotic bound (see Definition gif). For example, while it is not wrong to write tex2html_wrap_inline59115, we prefer to write f(n)=O(n), which is a tight bound.

Certain big oh expressions occur so frequently that they are given names. Table gif lists some of the commonly occurring big oh expressions and the usual name given to each of them.

 

 

expression name
O(1) constant 
tex2html_wrap_inline59121 logarithmic 
tex2html_wrap_inline59123 log squared 
O(n) linear 
tex2html_wrap_inline59127 n log n
tex2html_wrap_inline58403 quadratic 
tex2html_wrap_inline58715 cubic 
tex2html_wrap_inline59137 exponential 
Table: The names of common big oh expressions.


next up previous contents index

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