Complexity of algorithms: Difference between revisions
imported>Catherine Woodgold (O means "order".) |
imported>Catherine Woodgold (labelling exponential time) |
||
Line 13: | Line 13: | ||
* Super-polynomial time algorithms (grow faster than polynomial time algorithms). | * Super-polynomial time algorithms (grow faster than polynomial time algorithms). | ||
** <math>O(n!)</math> | ** <math>O(n!)</math> | ||
** <math>O(2^n)</math> | ** <math>O(2^n)</math> --- 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. | Despite the examples, with this notation one can express execution time as a function of multiple variables. |
Revision as of 14:00, 29 April 2007
In computer science, complexity of an algorithm is expressed by the worst-case execution time using the big O notation. It is generally written as , where is a function of zero or more parameters 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 for some positive constant K.
This 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.
Most commonly, one will see
- Polynomial time algorithms,
- --- Constant time --- the time necessary to perform the algorithm does not change in response to the size of the problem.
- --- Linear time --- the time grows linearly with the size (n) of the problem.
- --- 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).
- -- Logarithmic time
- Super-polynomial time algorithms (grow faster than polynomial time algorithms).
- --- 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 expected case is generally written as and the best case is written as .
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:
The term is irrelevant in the asymptotic case since it is dominated by the term. The constant factor is ignored. So we write the complexity of the bubble sort algorithm as . The expected and best cases are identical, so bubble sort is and .
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 . 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 , where:
However, if pivoting does not always split the array in half, then the worst case becomes .
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 , there exists a list length such that: