Determining Big-O Complexity

Submitted by fotios-dev on Mon, 2007-08-27 05:54

As a developer you will often wonder how complex is an algorithm or piece of code you are using, i.e. as the size of its input increases, at what rate does its use of computing resources (usually CPU cycles or memory) increase? In this sense any function of a program can be considered a mathematical function of x where x is the input to the function and f(x) is the number of computing resources used.

The symbol O denotes an asymptotic upper bound for a function in the form of another function that "bounds" it. So, f(x) is O(g(x)) or more simply f is O(g) basically means that the function f(x) has an upper bound determined by g(x). Therefore one can say that an algorithm or programming function is of O(g) where function g bounds how it claims computing resources as its input increases.

How to determine the O of an algorithm

The most important thing to remember when determining the O is that "stronger" terms of a function dominate its upper bound as the x get larger. So, for example, the function x + x² has an O(x²) simply because when x gets large enough the x² term of the function dominates.

The second most important thing to remember is that the O of your algorithm ultimately depends on the kind of programming statements it involves as well as how they are combined. The catch here is a statement that appears simple (i.e. O(1)) may actually involve some kind of lib or system call that is much more complex; so, look out for that! Note that O(1) basically means constant number of resources regardless of the size of input, e.g. a computation like x + 5 somewhere in your program basically always performs a integer addition regardless of how big x is.

Assuming all statements demoted as such are of O(1), here are some very basic rules:

Sequence of statements: O(1)
Loop of statements: O(n) where n is the number of loop executions. Note here that we assume n is the input of the function. If n is not related to the function's input then the loop is O(1) , i.e. constant.
Nested loop of statements: O(n*m) where n is the times the outer loop executes and m is the times the inner loop executes. Again, for this to make sense bothn and m must be somehow related to the input of the function. If n = m then we get an O(n²). In fact, this special case is, among others, the case of the well known Selection Sort algorithm (a quite inefficient algorithm actually but makes for a good N² example)

Some other common algos and their complexity orders, in order of growing magnitude, follow (from Wikipedia):

Big O Notation	Name	Example
$\mathcal{O}\left(1\right)$	constant	Determining if a number is even or odd
$\mathcal{O}\left(\log^* n\right)$	iterated logarithmic	The `find` algorithm of Hopcroft and Ullman on a disjoint set
$\mathcal{O}\left(\log n\right)$	logarithmic	Finding an item in a sorted list with the binary search algorithm
$\mathcal{O}\left(\left(\log n\right)^c\right)$	polylogarithmic	Deciding if n is prime with the AKS primality test
$\mathcal{O}\left({n^c}\right), 0<c<1$	fractional power	searching in a kd-tree
$\mathcal{O}\left(n\right)$	linear	Finding an item in an unsorted list
$\mathcal{O}\left(n\log n\right)$	linearithmic, loglinear, or quasilinear	Sorting a list with heapsort, computing a FFT
$\mathcal{O}\left({n^2}\right)$	quadratic	Sorting a list with insertion sort, computing a DFT
$\mathcal{O}\left({n^c}\right), c>1$	polynomial, sometimes called algebraic	Finding the shortest path on a weighted digraph with the Floyd-Warshall algorithm
$\mathcal{O}\left({c^n}\right)$	exponential, sometimes called geometric	Finding the (exact) solution to the traveling salesman problem (under the assumption that P ≠ NP)
$\mathcal{O}\left(n!\right)$	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
$\mathcal{O}\left(c_1^{c_2^n}\right)$	double exponential	Finding a complete set of associative-commutative unifiers [2]