Algorithm complexity

Complexity

Description

constant

O(1)

For performing an operation required constant number of steps (e.g., 1, 5, 10 or another number), and this number does not depend on the amount of input data.

Examples:

Making coffee for yourself every morning is O(1). Reading newspaper is probably O(logn) in terms of time vs interest

A simple example of O(1) might be return 23; -- whatever the input, this will return in a fixed, finite time.

O(1): Accessing an element in an array (i.e. int i = a[9])

O(1) - most cooking procedures are O(1), that is, it takes a constant amount of time even if there are more people to cook for (to a degree, because you could run out of space in your pot/pans and need to split up the cooking)

logarithmic

O(log(N))

To perform an operation on the N elements are necessary number of steps of the order of log (N), wherein the base of the logarithm is 2. The most commonly exemplary algorithm with complexity O (log (N)) for N = 1 million will make about 20 steps (to the nearest constant).

Examples:

A typical example if O(log N) would be looking up a value in a sorted input array by bisection.

divide and conquer as the example for O(log n)

O(log n): Binary search

O(logn) - finding something in your telephone book. Think binary search.

linear

O(N)

To perform an operation on N elements needed approximately as many steps as are the elements. For example, for 1000 the item need about 1000 steps. The number of elements and the number operations are linearly dependent, for example, the number of steps is about N / 2 or 3 * N for the N elements.

Examples:

O(n) - reading a book, where n is the number of pages. It is the minimum amount of time it takes to read a book.

O(n)

f(int n) {

  int i;

  for (i = 0; i < n; ++i)

    printf("%d", i);

}

O(n*log(n))

To perform an operation on N elements takes approximately N * log (N) steps. For example in 1000 the item takes about 10,000 steps.

Examples:

O(n log n): quick or mergesort (On average)

O(nlogn) - cant immediately think of something one might do everyday that is nlogn...unless you sort cards by doing merge or quick sort!

O (n log n) is famously the upper bound on how fast you can sort an arbitrary set (assuming a standard and not highly parallel computing model).

quadratic

O(n²)

For performing an operation required number of steps N2, where N characterizes the volume of the input data. For example, for an operation on 100 elements required 10,000 steps. If the number of steps in the square dependence of the volume of the input data, the complexity is quadratic.

cubical

O(n³)

For performing an operation required in the order of N3 steps, where N characterizes the volume of the input data. For example at 100 elements are implemented around one million steps.

exponential

O(2ⁿ), O(N!), O(n^k), …

For performing an operation or calculation required number of steps, which is an exponential dependence on the size of the input data. For example, when N = 10 exponential function 2N has the value 1024, when N = 20 is set to 1,048,576, and when N = 100 function has a value which is a number with 30 digits.