Complexity of algorithms

In computer science, Big O Notation is a notation for expressing the worst-case execution time for an algorithm.

It 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 O(f(x_1, x_2, \ldots, x_n))} , where 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 f} is a function of zero or more parameters $x_{i}$ of the system. It roughly states that in the aymptotic 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.

Big O Notation is attractive to computer scientists because it 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.

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. Please note that, by convention, one only writes the highest-degree term for polynomial time.
• Sub-polynomial time algorithms (grow slower than polynomial time algorithms).
  • $O(\log n)$ -- Logarithmic time
• Super-polynomial time algorithms (grow faster than polynomial time algorithms).
  • $O(n!)$
  • $O(2^{n})$

Despite the examples, Big O Notation can express execution time as a function of multiple examples.

Expected Case, Best Case

Similar analysis can be performed to find the expected and best case execution times of algorithms. The expected case is generally written as $\Theta (f(x_{1},x_{2},\ldots ,x_{n}))$ and the best case is written as $\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:

$O(\underbrace {{N \over {2}}\times \sum _{i=1}^{N}(N-i)} _{loops}\times \underbrace {1} _{if}\times \underbrace {1} _{swap})$

$=O({{N^{2}} \over {2}}+{{N} \over {2}})$

The ${N \over {2}}$ term is irrelevant in the asymptotic case since it is dominated by the ${{N^{2}} \over {2}}$ term. The constant $1 \over {2}$ factor is ignored. 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 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 \Theta(f(n))} , where:

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 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 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^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 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 K_1, K_2} , it must be the case that:

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 lim_{N\to\infty} K_1 \Theta(N^2) > K_2 \Theta(N \log N) }

See Also

• complexity theory
• complexity class