# Thread: Asymptotic bound on a modified insertion sort

1. 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  2.

3. 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
Must be final projects time or something, judging from the recent spate of thinly-veiled homework help requests from new members.  Bookmarks
 Posting Permissions
 You may not post new threads You may not post replies You may not post attachments You may not edit your posts   BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are On Terms of Use Agreement