he best case running time for insertion sort is when the input array is pre-sorted, like (1, 2, ..., n). In this case, insertion sort performs zero swaps and runs in O(n) time; even with no swaps, it still performs n iterations of its outer for loop. Suppose that we "cut" that array like a deck of cards to get the input array (i +1, i + 2, ..., n, 1, 2, ..., i) for some i E {1,..., n}. In terms of i and n, exactly how many swaps does insertion sort perform on this input, and what is its asymptotic (big-O) running time?