Big O Notation

Big O notation, or Big Oh notation, is often used to describe how the size of the input data affects an algorithm's usage of computational resources (usually running time or memory). Time and storage complexity are especially important on contests such as USACO, since you have a max running time of 1 second and a max storage of 1 MB. The notation O(f(n)) means that as n goes to infinity, the amount of operations or storage becomes f(n). If you have a small f(n), your program will run fast or take up a small amount of memory. Constants should never be included in Big O notation, which follows from the fact that n is always going to infinity. Here are some common Big O notations:

Notation Name
\$O(1)\$ Constant
\$O(\log n)\$ Logarithmic
\$O((\log n)^c)\$ Polylogarithmic
\$O(n^c), 0<c<1\$ Fractional Power
\$O(n)\$ Linear
\$O(n\log n)\$ Linearithmic, or loglinear
\$O(n^2)\$ Quadratic
\$O(n^c)\$ Polynomial
\$O(c^n)\$ Exponential
\$O(n!)\$ Factorial
\$O(n^n)\$ n to the n
page revision: 1, last edited: 12 Nov 2007 02:29
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License