Computing Students - Computer Science Degree Notes
Home Contact Shop Notes Questions Programming Links Dictionary Coursework FORUM Tutors
  Recommended Amazon Searches: Computer Science | Computing | Computer Systems | Database | Computing Revision  

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: Google | Kelkoo | Amazon | eBay (UK) | eBay (US)

Search for "Big-O Notation" on the rest of Computing Students: Big-O Notation

Home | Contact | Shop | Notes | Questions | Programming | Links | Dictionary | Coursework | Tutors Sponsored Links: Affiliate Program Articles | Computer Science Definitions | CS Degree Notes
Copyright © 2005-2009
This site is to be used in accordance with the User Agreement
High Wycombe Web Design