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

View edit of June 27, 2006 or FindPage with title or text search