Asymptotic complexity

A complexity of an algorithm state, how fast the algorithm is (how many elementary operations are performed) with respect to the input data set. For algorithm classification is usually used the so called asymptotic complexity. For every (asymptotic) complexity class it holds, that an algorithm from the previous class is for all input data greater than some lower bound always faster than an algorithm from the following class regardless of the speed of computers used to do this measurement (one computer may be c-times slower than the other (c is a constant)).

To distinguish classes of asymptotic complexity we may use scale of powers. It states that when data size approaches infinity, there exists no multiplicative constant , such that algorithm from the higher complexity class is faster than an algorithm from some lower class.

$1 \\ll \\log(n) \\ll n \\ll n \\cdot \\log(n) \\ll n^{k} \\ll k^{n} \\ll n! \\ll n^{n}$

What does it say?

$\\ln(x+1) \\in Ο(f(x^{2}))$

Suppose we have two algorithms of a comparable complexity – one has to perform O(n) operations and the second O(2n) , than we may run the second algorithm on a machine that is twice as fast and we won't be able to notice any difference between them. But if one algorithm has a complexity O(n) and the second O(n^2) , than there will not help any however fast computer. Because if we double the data, than the second computer will have to be 4 times faster. Provided that the data are ten times bigger, the computer will have to be 100 times faster...

In simple terms: if two algorithms belong to a different complexity class, than there always exist an input of some length, from which will be one of the algorithms always faster regardless of the speed of both computers.

In the illustration we can see that even if we multiply function x^2 by a very small constant (e.g. 0.001), there will still exist an intersection of both functions ( $x_{0}$ ), hence there will be some size of input, from which for all sizes of the input $x > x_{0}$ it holds, that the algorithm with complexity O(ln(x+1)) is always faster. By modifying the multiplicative constant we only move the intersection along the x-axis.

How the asymptotic complexity can be computed?

The asymptotic complexity can be computed as a count of all elementary operations, or more easily a count of all operations modifying data, or even only as a count of all comparisons. All these methods usually produce the same results.

Orders of growth

When analyzing most of the algorithms, we cannot determine exactly one complexity class, because the number of operations performed depends on the data itself. For example, we may say that the algorithms is in $\\Omega(n)$ and O(n^2) , which means that the algorithm will never terminate in less than operations, but on the other side its complexity is never worse than quadratic.

O(f(x)) – Omicron f(x) – algorithm always operates asymptotically better than or equally as f(x)

$O(f(x)) = \\{ g(x);\\; \\exists x_{0} \\gt 0,\\; c \\gt 0,\\; \\forall x \\gt x_{0} : g(x) \\lt c \\cdot f(x) \\}$

$\\Omega(f(x))$ – Omega f(x) – algorithm always operates asymptotically worse than or equally as f(x).

$\\Omega (f(x)) = \\{ g(x);\\; \\exists x_{0} \\gt 0,\\; c \\gt 0,\\; \\forall x \\gt x_{0}: c \\cdot f(x) \\lt g(x) \\}$

$\\Theta(f(x))$ – Omega f(x) – algorithm always operates asymptotically equally as f(x). That means the algorithm is in O(f(x)) and in $\\Omega(f(x))$ as well.

$\\Theta (f(x)) = \\{ g(x);\\; \\exists x_{0} \\gt 0,\\; c_{1} \\gt 0,\\; c_{2} \\gt 0,\\; \\forall x \\gt x_{0} : c_{1} \\cdot f(x) \\lt g(x) \\lt c_{2} \\cdot f(x) \\}$

Example

Java

    
    /**
     * Bubble sort
     * @param array array to be sorted
     */
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if(array[j] < array[j+1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                }
            }
        }
    }

The inner loop of this algorithm – bubble sort – is performed $(n-1) + (n-2) + (n-3) + \\cdots + 1$ times, which is according to the sum of the arithmetic progression $n \\cdot ((n-1) + 1)/2 = (n^{2}/2)$ operations. Because we are calculating the asymptotic complexity, we can omit the multiplicative contant. If the contained some additive constants, we would omit them as well. So the number of operations performed by bubble sort is n^2 . Because this calculation describes both best and worst case scenarios, the asymptotic complexity is $\\Theta(n^2)$ .

What does it say?

How the asymptotic complexity can be computed?

Orders of growth

Example

Doporučujeme