This topic contains 0 replies, has 0 voices, and was last updated by  EduGorilla 1 year, 11 months ago.

  • Author
    Posts
  • #1440026 Reply
     EduGorilla 
    Keymaster
    Select Question Language :


    Suppose we modify merge sort in the following two ways :
    • We split the input into three equal segments, recursively sort each segment and then do a three way merge of the three sorted segments to obtain a fully sorted output.
    (Let us call this as 3 way merge sort)
    • We split the input into two unequal segments, first segment contains only one element and other segment is biased to the right side, recursively sort each segment and then do a two way merge of the two sorted segments to obtain a fully sorted output.
    (Let us call this as biased merge sort)
    What can we say about the asymptotic worst case complexity of merge sort , 3 way merge sort and biased merge sort ?

    Options :-

    1. The asymptotic complexity of 3 way merge sort and biased merge sort is more than 2 way merge sort.
    2. The asymptotic complexity of 3 way merge sort and biased merge sort is less than 2 way merge sort.
    3. The asymptotic complexity of biased merge sort is more than 2 way merge sort and 3 way merge sort.
    4. The asymptotic complexity of biased merge sort is less than 2 way merge sort and 3 way merge sort.
    Post your Training /Course Enquiry
    Are You looking institutes / coaching center for
    • IIT-JEE, NEET, CAT
    • Bank PO, SSC, Railways
    • Study Abroad
    Select your Training / Study category
Reply To: Suppose we modify merge sort in the following two ways : • We split the input into three equal se….
Your information:




Verify Yourself




Log in with your credentials

or    

Forgot your details?

Create Account