How do you manipulate Insertion Sort to always run in the worst case complexity

Question

I have to implement a hash function that takes an array and a index as the arguments and returns an integer. I then have to use this hash function to cause Insertion Sort to always run in the worst case complexity even if the resulting array does not end up getting sorted.

Pseudocode below:

function INSERTIONSORT(A[0..n − 1])
for i ← 1 to n − 1 do
     j ← i − 1
     while j ≥ 0 and HASH(A, j + 1) < HASH(A, j) do
          SWAP(A[j + 1], A[j])
          j ← j − 1

I know that the worst case complexity of insertion sort is O(n²), but if I made HASH(A, j + 1) return an integer which is always less than HASH(A, j) so that the while loop runs for its maximum amount of loops, would that achieve O(n²) time complexity?

Answer 1

I think the last question "would that achieve O(n²) time complexity?" itself is wrong.
It obviously achieve O(n²) time complexity, how couldn't it?

If you want to work always in the worst-case scenario, besides O(n²) you basically want also to ensure o(n²), i.e. you want to fix a lower bound which is equal to the upper bound.

Anyway, the answer is still yes: mading HASH(A, j + 1) returning an integer which is always less than HASH(A, j), you ensure that the inner loop always runs i times. So for any execution you will do exactly 1+...+(n-1), which is quadratically (both lower and upper) bounded.