Big O Notation is based on complexity theory and is something engineers and architects should know about do determine complexity and orders of magnitude in their data and scalability formal blueprints. Whenever you use any algorithm or port a formal function into code, math and reducing the orders of magnitude is what separates the fast from really fast.

Optimization can be evil, but solid base starting points are desired. Many times formal knowledge can be as needed as logical or physical separation and understanding service and standards format layering in your applications for the best evolution and versioning as well as performance. Formal engineering is what is separating companies like Google from the pack. Do you do formal?

Orders of common functions

Here is a list of classes of functions that are commonly encountered when analyzing algorithms. All of these are as n increases to infinity. The slower-growing functions are listed first. c is an arbitrary constant.

Notation	Name	Example
	constant	Determining if a number is even or odd
	inverse Ackermann	Amortized time per operation when using a disjoint-set (union-find) data structure
	iterated logarithmic	The find algorithm of Hopcroft and Ullman on a disjoint set
	logarithmic	Finding an item in a sorted list with the binary search algorithm
	polylogarithmic	Deciding if n is prime with the AKS primality test
	fractional power	searching in a kd-tree
	linear	Finding an item in an unsorted list
	linearithmic, loglinear, or quasilinear	Sorting a list with heapsort, computing a FFT
	quadratic	Sorting a list with insertion sort, computing a DFT
	polynomial, sometimes called algebraic	Finding the shortest path on a weighted digraph with the Floyd-Warshall algorithm
	exponential, sometimes called geometric	Finding the (exact) solution to the traveling salesman problem (under the assumption that P ≠ NP)
	factorial, sometimes called combinatorial	Determining if two logical statements are equivalent[1], traveling salesman problem, or any other NP-complete problem via brute-force search, finding the determinant of a matrix with expansion by minors
	n to the n
	double exponential	Finding a complete set of associative-commutative unifiers[2]

Not as common, but even larger growth is possible, such as the single-valued version of the Ackermann function, A(n,n). Conversely, extremely slowly-growing functions such as the inverse of this function, often denoted α(n), are possible. Although unbounded, these functions are often regarded as being constant factors for all practical purposes.

Tags: architecture, chaos, complexity, design, formal, mathematics, simulation, theory

This entry was posted on Saturday, March 22nd, 2008 at 7:01 pm and is filed under baseplane, formal, market formats, philosophy, programming, standards, technology. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.