Notes > Computation and Algorithms > Big-O Notation
Algorithms can be associated with an equation which defines the number of steps the algorithm takes, typically in terms of "n" (e.g. n2/2 + 3). To categorise algorithms into certain groups, Big-O notation is used. The equation n2/2 + 3 would mean that the algorithm associated with it is of order O(n2).
Big-O notation igonores any constant factors and any lower order factors of n. Take another example of n2 + n + 1 which would also be of order O(n2). See Program Complexity for more information.
The following list gives some names and examples of the common orders used to describe functions. These orders are ranked from fast (top) to slow (bottom).
- Logarithmic - O(log n)
- Linear - O(n)
- Linearithmic - O(n log n)
- Quadratic - O(n2)
- Exponential / Geometric - O(cn)
Search for "Big-O Notation" on:
eBay (UK) |
Search for "Big-O Notation" on the rest of Computing Students: Big-O Notation