This running time can be expressed as an b for constants a and b that depend on the statement costs ci ; it is thus a linear function of n.
If the array is in reverse sorted order-that is, in decreasing order-the worst case results. We must compare each element A[j] with each element in the entire sorted subarray A[1 ‥j - 1], and so tj = j for j = 2, 3, . . . , n. Noting that
we find that in the worst case, the running time of INSERTION-SORT is
This worst-case running time can be expressed as an2 bn c for constants a, b, and c that again depend on the statement costs ci ; it is thus a quadratic function of n.
Typically, as in insertion sort, the running time of an algorithm is fixed for a given input, although in later chapters we shall see some interesting "randomized" algorithms whose behavior can vary even for a fixed input.
In our analysis of insertion sort, we looked at both the best case, in which the input array was already sorted, and the worst case, in which the input array was reverse sorted. For the remainder of this book, though, we shall usually concentrate on finding only the worst-case running time, that is, the longest running time for any input of size n. We give three reasons for this orientation.