To characterize runtimes we discard the low-order terms and the coefficients of the leading term as done with insertion sort in Chapter Two. The remaining factor is put into the -notation e.g . Other asymptotic notations are designed to characterize functions in general. Asymptotic notation can apply to functions that characterize some other aspect of algorithms e.g. space or other functions not relating to algorithms.
The O-notation
This notation expresses a function that doesnโt grow faster than a certain rate based on the highest-order term. Considering a function with the highest order term as , the rate of growth of this function is . This function can be expressed as , considering it doesnโt grow faster than .
We could also say the function is , , , because grow slower than them, hence we could say: is for any constant .
The -notation
The is used to express that a function grows at least as fast as a certain rate, based on the highest order term. This can be seen as the inverse of the O-notation.
Similarly, it can grow as fast as , , hence we can say for any constant .
The -notation
This expresses that a function grows exactly at a certain rate based on the highest-order term. It expresses that a function does not grow above or below a certain factor, and these factors need not be equal.
It can also be expressed as the result of showing that a function is both O(f(n)) and \Omega(f(n)). For example, the above, showing that is both and , it is also .
An Example: Insertion sort
From the insertion sort procedure in Chapter 2:
INSERTION-SORT (A, n) for i = 2 to n key = A[i] j = i - 1 while j > 0 AND A[j] > key A[j+1] = A[j] j = j - 1 A[j + 1] = key
The procedure operates using nested loops, the outer loop runs times regardless of the values being sorted. The inner while loop iterates based on the number of values to be sorted. For a value , the while loop might iterate times, times or anywhere in between in constant time.
We can say Insertion sort is since each iteration of the inner loop takes constant time .
We could also say the worst case is because for every input size n, there is at least one input that makes the algorithm take at least time, for some constant c. This does not mean the algorithm takes at least time for all inputs.
To understand why the worst case time of
INSERTION-SORT
is , we would assume the size of an array is a multiple of . Divide into groups of positions. If the largest values occupy the first array positions , once the array is sorted, each of these array values ends up somewhere in the last positions . And for this to happen, each of these values must pass through each of the middle n/3 position one at a time. At least executions of line 6 must have happened. Because values have to pass through positions, the worst case of INSERTION-SORT
is at least proportional to = , which is .Now that we have shown that that
INSERTION-SORT
runs in in all cases and there is an input that makes it take , hence, the worst case running time of INSERTION-SORT
is .The constant factors for upper bound or lower bound might differ, what matters is that we have characterized the worst-case running time to within constant factors(ignoring the lower-order-terms). This does not mean
INSERTION-SORT
runs in in all cases, in fact, the best case running time for INSERTION-SORT is as shown in chapter 2.Asymptotic notation: formal definitions
ย
ย
ย