Complexity of algorithms

In computer science, the complexity of an algorithm is a way to classify how efficient an algorithm is, compared to alternative ones. The focus is on how execution time increases with the data set to be processed.

Informal definition

The complexity of a given algorithm is expressed by the worst-case execution time, using the big O notation. It is generally written as $O(f(x_{1},x_{2},\ldots ,x_{n}))$, where $f$ is a function of one or more parameters $x_{i}$ of the system. The "O" is read "order" as in "order of magnitude" or "on the order of". It roughly states that in the asymptotic case (i.e. as one or more of the system parameters extend towards their extremes), the actual execution time of the algorithm is bounded by $K\times f(x_{1},x_{2},\ldots ,x_{n})$ for some positive constant K.

Sometimes one is interested in expected or best case execution time as well, or even the algorithms requirements of memory or other resources.

The big O notation expresses the complexity of an algorithm without restricting the statement to a particular computer architecture or time period; even if computers get faster, or if the algorithm is ported to another software platform, the worst case execution time of an algorithm does not change. Additionally, when comparing two algorithms, it is readily apparent which will execute faster in the extreme case.

Classes of complexity

Most commonly, one will see

• Polynomial time algorithms,
  • $O(1)$ --- Constant time --- the time necessary to perform the algorithm does not change in response to the size of the problem.
  • $O(n)$ --- Linear time --- the time grows linearly with the size (n) of the problem.
  • $O(n^{2})$ --- Quadratic time --- the time grows quadratically with the size (n) of the problem. In big O notation, all polynomials with the same degree are equivalent, so Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(3n^2 + 3n + 7)=O(n^2)}
• Sub-linear time algorithms (grow slower than linear time algorithms).
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(\log n)} -- Logarithmic time
• Super-polynomial time algorithms (grow faster than polynomial time algorithms).
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n!)}
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(2^n)} --- Exponential time --- the time required grows exponentially with the size of the problem.

Despite the examples, with this notation one can express execution time as a function of multiple variables.

Expected case, best case

Similar analysis can be performed to find the expected and best case execution times of algorithms. The best case is generally written as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega( f(x_1, x_2,\ldots, x_n))} .

Example of finding the complexity of an algorithm

Bubble sort

Take, for example the bubble sort algorithm for sorting a list of numbers,

 Procedure: BubbleSort(List[])
 Inputs: List[] - A list of numbers
 Locals: i, j - integers
 Begin:
    For i = 0 to List.Size-1
       For j = i+1 to List.Size-1
          If List[i] > List[j], Then
             Swap List[i] and List[j]
          End If
       Next j
    Next i

The size of the sorting problem is related to the size N of the list. As N increases, we expect the execution time to increase as well. To find the complexity of this algorithm, we start from the middle and work our way out.

The innermost instruction is to swap two list elements. Irregardless of how long the list is, this always takes the same amount of time, and so the swap instruction is O(1) with respect to N. Surrounding that instruction is an if statement, which either executes its body, or does not; in the worst case, it will execute its body. Again, the if statement is O(1).

The if statement is executed as many times as the inner loop iterates, and the inner loop executes as many times as the outer loop interates. During the first iteration (i=0), the inner loop executes N-1 times, during the second iteration (i=1), N-2 times, and so on. So, our complexity for this algorithm is:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O( \underbrace{ \sum_{i=1}^N (N-i) }_{\textrm{number-of-loops}} \times (\underbrace{\underbrace{1}_{if} + \underbrace{1}_{swap}}_{\textrm{time-per-loop}}) ) }

$=O(N^{2}-N)$

The $N$ term is irrelevant in the asymptotic case since it is dominated by the $N^{2}$ term. So we write the complexity of the bubble sort algorithm as $O(N^{2})$. The expected and best cases are identical, so bubble sort is $\Omega (N^{2})$ and $\Theta (N^{2})$.

Quick sort

It is important to understand that complexity as we have discussed here pertains to the algorithm, not to the problem. As was noted earlier, the bubble sort algorithm has complexity of $O(N^{2})$. However, sorting a list of numbers can be done more efficiently. Take, for instance, the quick sort algorithm:

  Procedure: QuickSort(List[])
  Inputs: List[] - A list of numbers,
  Locals: Left[] - A list of numbers, initially empty
          Right[] - A list of numbers, initially empty
          PivotElement, Elt - numbers
  Begin:
     If List.Size > 1, Then
        Let PivotElement = List[ List.Size / 2 ]
        For each element Elt in List[], do
           If Elt <= PivotElement, Then
              Append Elt to Left[]
           Else
              Append Elt to Right[]
           End If
        Next
        QuickSort(Left[])
        QuickSort(Right[])
        Let List[] = Left[] concatenate Right[]
     End If

This algorithm is more difficult to analyze because it involves recursion, but is nonetheless possible. Again, we work from the inside out. Appending an element to a list is O(1), and so is the innermost if statement. Additionally, list concatenation is O(1) The pivoting loop executes once for each element in the list, and thus the loop is O(N).

If we assume that, pivoting loop splits List[] into two halves of equal size (i.e. both Left[] and Right[] have N/2 elements) then, the expected complexity of the quick sort algorithm is $\Theta (f(n))$, where:

$f(n)=\underbrace {N} _{loop}+\underbrace {2\times f({{N} \over {2}})} _{recursion}=N\log N$

However, if pivoting does not always split the array in half, then the worst case becomes $O(N^{2})$.

The quick sort algorithm can thus be shown to be more efficient in the expected case. Once the problem size grows large enough, bubble sort must take more time. More formally, for any positive constants $K_{1},K_{2}$, there exists a list length $N_{0}$ such that:

$\forall N>N_{0}:K_{1}\Theta (N^{2})>K_{2}\Theta (N\log N)$