0
$\begingroup$

I am working on the following problem, given input list of length n to two sublists of length n2 , which are recursively sorted and then merged into a sorted list of length n. The merge sort has the recurrence for its time complexity as T (n) = 2T (n/2) + O(n). We can assume that the algorithm is modified such that the input list is split into two sublists of lengths n and n/2, respectively, which are recursively sorted and then merged into a sorted list of length n.

The two main problems that I am trying to solve are:

  1. Give a recursive definition of the worst case time function T (n) for this variant of mergesort;

  2. If the algorithm is again modified to split the list into two sublists of lengths n/10 and 9n/10 what should the time function T(n) be in a recursive form?

  3. Given the algorithm for Mergesort


Input:   Anarray of numbers :a[1...n] 
Output:  A sorted version of this array
function mergesort(a[1 . . . n])    
    if n > 1: return 
        else: return merge(mergesort(a[1 . . . ⌊n/2⌋]), mergesort(a[⌊n/2⌋ + 1 . . . n])) a

Then


T(n) = c1  n = 1 else 2*T(n/2) + O(n)
  1. Given the modified algorithm for Mergesort
Input:   Anarray of numbers :a[1...n] 
Output:  A sorted version of this array
function mergesort(a[1 . . . n])    
    if n > 1: return 
        else: return merge(mergesort(a[1 . . . ⌊n/2⌋]), mergesort(a[⌊n/2⌋ + 1 . . . n])) a 
function mergesort(a[1 . . . n])    
    if n > 1: return 
        else: return merge(mergesort(a[1 . . . ⌊n/10⌋]), mergesort(a[⌊9n/10⌋ + 1 . . . n])) a

Then

T(n) = c1  n = 1 else 10*T(n/10) + O(n)

I would appreciate it if someone could verify this solution. There is never enough time, thank you for yours. Thank you for your integrity. Thank you for your humility. Thank you for your presence.

V.R. E. M. Gertis

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I think you have made a typing error which makes the question unclear. It would be helpful if you edited to make life easier for people. “given input list of length n to two sublists of length n2” looks as if there is a word missing, and you do not define “n2” anywhere. Did you mean $\frac n 2$? $\endgroup$
    – Martin Kochanski
    Commented Jan 27, 2023 at 14:44
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W. ♦
    Commented Jan 27, 2023 at 23:33
  • $\begingroup$ There seems to be something wrong with given input list of length n to two sublists of length n2 as well as with two sublists of lengths n and n/2. $\endgroup$
    – greybeard
    Commented Jan 28, 2023 at 7:46

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.