Asymptotic bound on a modified insertion sort
I have a problem that I don't know how to begin with. I know that insertion sort is O(n) but how to I add the special string comparison?
Consider the code for INSERTION-SORT, given below. Now Assume that your elements in the array are strings. For simplicity,
assume all strings to be of the same length s. Also assume that the comparision A[i] > key on line 5 is not a constant time
operation, but instead linear in the size of the strings compared, i.e. it is O(s).
Derive an asymptotically tight upper bound on the worst case of INSERTION-SORT under these new circumstances. That is,
find a function f(n,s) such that INSERTION-SORT is O(f(n,s)).
Insertion-Sort(A)
1 for j <- 2 to length(A)
2 do key <- A[j]
3 |> Insert A[j] into A[1..j-1].
4 i <- j-1
5 while i > 0 and A[i] > key
6 do A[i-1] <- A[i]
7 i <- i-1
8 A[i-1] <- key
