Order Notation

The mathematician's notation used for describing the asymptotic behaviour of a function.

Uses the symbols O (BigOh), o (LittleOh?), Ω (BigOmega), (BigTheta), and others.

In particular, BigOh and BigTheta are much-used in expressions relating to algorithm complexity. Hence their use should be covered in computer science courses.

Such usage has led to changes in formal definitions, so that "is in O(n)" is displacing "= O(n)".

Q: Citation on this change in formal definition?

A: See the definitions in http://www.cs.msstate.edu/~bridges/cs8833/2004/lecture02.ppt, whereas the references to sets of functions are not used in Pure Mathematics by Hardy and Wright.

CategoryMath, CategoryPerformance

EditText of this page (last edited June 27, 2006) or FindPage with title or text search