Notices
Results 1 to 2 of 2

Thread: Asymptotic bound on a modified insertion sort

  1. #1 Asymptotic bound on a modified insertion sort 
    New Member
    Join Date
    Dec 2012
    Posts
    2
    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


    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Isotope
    Join Date
    Feb 2012
    Location
    Western US
    Posts
    2,945
    Quote Originally Posted by M-aria View Post
    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.


    Reply With Quote  
     

Similar Threads

  1. Retrovirus RNA Insertion, Random?
    By Erebus in forum Biology
    Replies: 3
    Last Post: March 7th, 2011, 07:03 PM
  2. Replies: 3
    Last Post: February 24th, 2011, 08:58 AM
  3. Replies: 18
    Last Post: January 7th, 2008, 03:13 PM
  4. Dembski`s Universal Probability Bound...
    By DeCatte in forum Pseudoscience
    Replies: 22
    Last Post: September 17th, 2007, 05:05 AM
  5. Two Neutron Bound State
    By Petroleum in forum Physics
    Replies: 0
    Last Post: January 4th, 2007, 01:24 AM
Bookmarks
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
  •