Question

If I is the number of inversions in an input array of n records, then Insertion Sort will run in what time?

Answer 1

Insertion Sort has a time complexity of O(n + i), where n is the number of elements and i is the number of inversions in the input array.

Step-by-step explanation:

Insertion Sort is an algorithm used to sort an array of elements. The time complexity of Insertion Sort is determined by the number of inversions in the input array. In an array with n elements and i inversions, the time complexity of Insertion Sort is O(n + i).

For example, let's say we have an array with 5 elements and 8 inversions. In this case, the time complexity of Insertion Sort would be O(5 + 8) = O(13).

Therefore, the time complexity of Insertion Sort is directly related to the number of inversions in the input array.