ZuoTi.Pro
Question

Find the space complexity of Merge Sort below as a function of n (the length of A). Assume: • The elements of A require (1) s

engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

solution:

Given data:

In merge sorting when we are merging the 2 sorted array we create 2 temporary array.

Let

L[ ]=Arr[left,mid] (left array )

R[ ]=Arr[mid+1,right] (right array )

To temporarily store the old array from left to mid(sorted left half) and R[ ]=Arr[mid+1,right](right array ) to temporarily store the old array from mid+1 to right(sorted right half) ,then we merge the two temporary array into the original one .
The fact that we create 2 temporary array to store the numbers of the original array , since the original array has n elements the temporary arrays are of size n respectively and hence the extra space of n and an O(n) space complexity.

In the given question we have

Input A which require constant space = O(1)

A1=O(n/2)

A2=O(n/2)

A is not being sorted in place for sorting.

The original space of the array is not accounted while calculating the space complexity of a sorting algorithm.

So, space complexcity => O(n).

please give me thumb up

0 0
Add a comment
Know the answer?
Add Answer to:
Find the space complexity of Merge Sort below as a function of n (the length of...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • HW58.1. Array Merge Sort You've done merge (on Lists), so now it's time to do merge...

    HW58.1. Array Merge Sort You've done merge (on Lists), so now it's time to do merge sort (on arrays). Create a public non-final class named Mergesort that extends Merge. Implement a public static method int[] mergesort(int[] values) that returns the input array of ints sorted in ascending order. You will want this method to be recursive, with the base case being an array with zero or one value. If the passed array is null you should return null. If the...

  • 1.) Complete the merge method below, which is the merge step of MergeSort. That is, it...

    1.) Complete the merge method below, which is the merge step of MergeSort. That is, it takes two sorted arrays as input and returns a new sorted array that contains all the elements from the two input arrays. Furthermore, it should keep all duplicated values, and it should run in O(n) time, where n is the size of the output array. public static int[] main(int[] a, int[] b) { }

  • Please merge all the codes below and add comments using JAVA Program. I need a complete...

    Please merge all the codes below and add comments using JAVA Program. I need a complete code which is the combination of the following codes: // Merges the left/right elements into a sorted result. // Precondition: left/right are sorted public static void merge(int[] result, int[] left,                                        int[] right) {     int i1 = 0;   // index into left array     int i2 = 0;   // index into right array     for (int i = 0; i < result.length; i++)...

  • In this assignment you will implement merge-sort algorithm by creating 2 threads instead of 2 pro...

    In this assignment you will implement merge-sort algorithm by creating 2 threads instead of 2 processes. First half of the array will be sorted by thread 1 and the second half by thread 2. When the threads complete their tasks, the main program will merge the half arrays. You should not waste your time on merge-sort algorithm. Use the merge sort algorithm given below void mergesort(int a[],int i,int j) { int mid; if(i<j) { mid=(i+j)/2; mergesort(a,i,mid); //left recursion mergesort(a,mid+1,j); //right...

  • Create a program called Merge.java that implements a variety of the Merge function (in the Merge...

    Create a program called Merge.java that implements a variety of the Merge function (in the Merge Sort algorithm). The program should be able to do the following: accepts two command line parameters, each specifies a text file containing the integers to be merged. The structure of the files is as follows: For both files, there will be multiple lines, each of which contains one integer. The number of lines is unknown. reads the integers from the text files into two...

  • Modify the sorts (selection sort, insertion sort, bubble sort, quick sort, and merge sort) by adding code to each to tally the total number of comparisons and total execution time of each algorithm. E...

    Modify the sorts (selection sort, insertion sort, bubble sort, quick sort, and merge sort) by adding code to each to tally the total number of comparisons and total execution time of each algorithm. Execute the sort algorithms against the same list, recording information for the total number of comparisons and total execution time for each algorithm. Try several different lists, including at least one that is already in sorted order. ---------------------------------------------------------------------------------------------------------------- /** * Sorting demonstrates sorting and searching on an...

  • Consider a variation of Merge sort called 4-way Merge sort. Instead of splitting the array into...

    Consider a variation of Merge sort called 4-way Merge sort. Instead of splitting the array into two parts like Merge sort, 4-way Merge sort splits the array into four parts. 4-way Merge divides the input array into fourths, calls itself for each fourth and then merges the four sorted fourths. a)Implement 4-way Merge sort from Problem 4 to sort an array/vector of integers and name it merge4. Implement the algorithm in the same language you used for the sorting algorithms...

  • Please give a output Linux/Ubuntu and how to run it (compile) this program ,my assigment is below...

    Please give a output Linux/Ubuntu and how to run it (compile) this program ,my assigment is below : : Merge Sort algorithm using 2 processes a.) Define an integer array of 100 integers. Populate this array with random numbers. You can use int rand(void); function. Do not forget to initialize this function. You will sort the numbers in the array using merge-sort algorithm. In merge sort algorithm the half of the array will be sorted by one process and second...

  • Implement Merge Sort and test it on a small list of 10 random integer values. c++...

    Implement Merge Sort and test it on a small list of 10 random integer values. c++ please template            // merge-sort S void mergeSort(list& S, const C& less) { typedef typename list::iterator Itor;       // sequence of elements int n = S.size(); if (n <= 1) return;                   // already sorted list S1, S2; Itor p = S.begin(); for (int i = 0; i < n / 2; i++) S1.push_back(*p++);   // copy first half to...

  • (9) Complete the below Java method recursively, which takes in a String and returns if it's...

    (9) Complete the below Java method recursively, which takes in a String and returns if it's a palindrome. Remember a palindrome means a string that is the same reversed, like "deed", "racecar" or "tacocat". The empty string "" is also a palindrome. public boolean isPalindrome (String word) { (8) (a) (8 points) Implement merging two sorted arrays into one sorted ar- ray. These arrays are sorted in descending order. For example, (5, 4, 2). Return an array with all the...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT