Final answer:
The running time of Insertion Sort when the input is an array that has already been sorted is O(n), where n is the number of elements in the array.
Step-by-step explanation:
The running time of Insertion Sort when the input is an array that has already been sorted is O(n). This means that the time it takes to sort the array is directly proportional to the number of elements in the array.
When the input array is already sorted, Insertion Sort becomes more efficient because it only needs to compare each element with the element before it in order to determine its correct position. Since the elements are already sorted, this comparison results in a constant time complexity.
For example, if you have an array with 10 elements, it would take 10 comparisons to sort it. If you have an array with 100 elements, it would take 100 comparisons to sort it.