Big-O notation describes the time/processing requirement for an algorithm. Only the highest order term (fastest growing) is displayed, so for very small input sets it may be inaccurate. For example, if an algorithm takes x^3 + 10000x seconds to perform a task, the Big-O (order) is x^3 -- clearly misleading. As x tends toward infinity, however, it is more accurate.

Note: in the following, we assume that all functions map from a totally ordered set to the reals. Usually when discussing big-oh notation, functions map from nonnegative integers to nonnegative integers or from nonnegative integers to nonnegative reals, but the following defintions are more general.

A function f is O(g) iff there exist a nonzero constant M and a constant N such that, for every n > N, |f(n)| <= |Mg(n)|. Exercise: let P be a totally ordered set with a greatest element m, and let f, g be functions from P to R such that g(m) != 0. Prove that f is O(g).

Notice that this is a weak bound. For example, f(x) = x²+7 may be said to be O(x²), but it may also be said to be O(x³) or O(e^x).

Change <= to < in the above, and you have little-oh notation. Change <= to >=, and you have big-omega notation. Change <= to >, and you have little-omega notation.

There is also big-theta notation. f is Θ(g) iff there exist nonzero constants M₁ and M₂ and a constant N such that, for every n > N, |M₁g(n)| <= |f(n)| <= |M₂g(n)|. This is a stricter version of big-oh and big-omega notation. f is Θ(g) iff f is both O(g) and Ω(g).

One may use the above to define a relation: f ~ g iff f is Θ(g). It is easy to show that ~ is reflexive, symmetric, and transitive. Thus it is an equivalence relation, and partitions the set of functions into a number of equivalence classes. We call these complexity classes; the complexity class containing f is called Θ(f). Then we can say things like f ∈ Θ(g), which can make definitions and proofs simpler to write in some cases.

Important classes for real-valued functions of one integer variable:

• Θ(1) (constant)
• Θ(log*(n)) (iterated logarithmic)
• Θ(log(log(n)) (bilogarithmic)
• Θ(log(n)) (logarithmic). Note that Θ(ln(n)) = Θ(log(n)) = Θ(lg(n)), because they are related by constant ratios.
• Θ(n) (linear)
• Θ(n log(n))
• Θ(n²) (quadratic)
• Θ(2ⁿ) (base-two exponential)
• Θ(eⁿ) (natural exponential)
• Θ(A(n,n)) (an example of a hyperexponential complexity class).

This notation is used as a measure of complexity.

Personally, I find the standard definition ("if there exists a constant such that for all N>n") to be annoyingly obfuscated. A much simpler way (IMO) to state it:

• f(x) is in big-oh(g(x)), if lim_n->inf.( f(n)/g(n) ) is less than infinity.
• f(x) is in small-oh(g(x)), if lim_n->inf.( f(n)/g(n) ) is zero.
• f(x) is in theta(g(x)), if lim_n->inf.( f(n)/g(n) ) is finite but not zero

(Assuming that all f(x) and g(x) only have positive values, otherwise you have to take absolute values)

Big-oh notation is a way of describing the change in how long an algorithm will take to run based on the number of input values it must process. It is independent how fast the computer can make calculations. It is also independent of the type of programming language used to execute the algorithm. Big-oh notation is the highest order nomial of a runtime efficency equation.

Let n equal the number of input values for a given algorithm.

Here are some basic types of big-oh notations:
The ones that take the least amount of computations are listed first.

• Constant: O(1) - pronounced "order one" or "constant order"
• Logarithmic: O(log n) - pronounced "order log n" or "logarithmic order"
• Linear: O(n) - pronounced "order n" or "linear order"
• "N log n": O(n*logn)
• Quadratic: O(n²) - pronounced "order n squared" or "quadratic order"
• Cubic: O(n³) - pronounced "order n cubed" or "cubic order"
• Exponential: O(2ⁿ) - pronounced "order two to the power of n" or "exponential order"

If an algorithm has a constant order, O(1), it takes the same amount of time to process 1 element as it does to process 1000 elements. It does not matter how many input elements there are. The run time will always be the same for an order one algorithm. For example, an algorithm is made to return the first number of a list of any size. The algorithm does not care how big the list is. All it needs to complete its objective is the first number of the list. Thus, the big-oh notation is order one.

An algorithm with a linear order, O(n), will take n times as long to run if it has n input values only in the worst case scenario. For example, consider an algorithm that must search a list (or array) of numbers for the highest value present. At best the algorithm must compare n elements and only at the first comparison assign that maximum value to a variable. At worst it must compare n elements and continually reassign the maximum value (for further comparision) to a variable. In the worst case, it still has to go through n elements. Therefore the algorithm is O(n).

C++ example of O(n) algorithm:
// Assume list[] is an initialized array with n elements.
int largest_num(int list[], int n)
{
   int max = 0;
   for( int i=0; i<=n; i++ )
      if( list[i] > max )
         max = list[i];
   return max;
}


Sample cases (each with 5 elements in the array):
Best case - 5, 4, 3, 2, 1. One assignment to max is made.
Worst case - 1, 2, 3, 4, 5. Five assignments to max are made.

The same kind of logic applies to all other notations. For a quadratic order the runtime takes n² as long (in the worst case possible) to process n elements, and so on.

Big-oh notation is useful when comparing the efficiency of various sorting and searching algorithms to one another. Listed below are some algorithms and their corresponding big-oh notations:

• Selection sort
  • All cases: O(n²)
• Insertion sort
  • Best case: O(n)
  • Average case: O(n²)
  • Worst case: O(n²)
• Quicksort
  • Best case: O( n*log n )
  • Average case: O( n*log n )
  • Worst case: O( n² )
• Merge Sort
  • All cases: O( n*log n )
• Binary tree sort (or heap sort):
  • All cases: O( n*log n )
• Sequential search:
  • All cases: O(n)
• Binary search:
  • Best case: O(1)
  • Average case: O(log n)
  • Worst case: O(log n)
• Hash insertion and searching (ideal):
  • All cases: O(1)

More information on algorithms and their runtimes can be found at the NIST's Dictionary of Algorithms and Data Structures web page - http://www.nist.gov/dads/

Source for this writeup: Barron's How to Prepare for the AP Computer Science Advanced Placement Examination.