Originally Posted by

**M-aria**
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