Runtime complexity of insertion sort for half sorted array and half reversed sorted

Question

Wondering what is the average runtime complexity for half sorted and half reverse sorted array. For example the array: [0,7,2,5,4,3,6,1], number on every even index is sorted and number on odd index is reverse sorted. Would the runtime be O(n) or O(n^2)? Thanks!

Answer 1

The time complexity would be O(n^2). The rationale behind this is that the reversed sorted array is a subset of the original array, so even skipping any work associated with the sorted elements, its still going to do O((n/2)^2) = O(n^2) work to sort those. Adding other elements to the list won't remove any of those steps (any comparisons done on the subset will also be performed on the full list, in order, just possibly not consecutively). It also won't push it past O(n^2), because insertion sort has a worst-case time complexity of O(n^2), so we're bounded from below by the time complexity of a subproblem, and bounded above by the theoretical worst-case, so its overall time complexity is O(n^2).