ZuoTi.Pro
Question

suppose we are comparing implementations of insertion sort and merge sort on the same machine. For...

suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n^2 steps, while merge sort runs in 64n lg n steps. For which values of n does insertion sort beat merge sort?

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

Homework Answers

Answer #1

As it is specified that, insertion sort runs in  8n^2 steps, while mergesort runs in 64n lg n steps.

The table of various values of n for insertion sort and merge sort is:

n insertion sort mergesort
2 32 88
3 72 210
4 128 354
5 200 515
10 800 1473
20 3200 3834
25 5000 5150
26 5408 5421
27 5832 5695

Therefore, for n values that are less than 27, insertion sort is better than mergesort, and for all n values that are greater than or equal to 27, mergesort is better than insertionsort.

0 0
Add a comment
Know the answer?
Add Answer to:
suppose we are comparing implementations of insertion sort and merge sort on the same machine. For...
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

  • Insertion sort on small arrays in merge sort Although merge-sort runs in Θ(n log n) worst-case...

    Insertion sort on small arrays in merge sort Although merge-sort runs in Θ(n log n) worst-case time and insertion sort runs in Θ(n 2 ) worst-case time, the constant factors in insertion sort can make it faster in practice for small problem sizes on many machines. Thus, it makes sense to coarsen the leaves of the recursion by using insertion sort within merge sort when subproblems become sufficiently small. Consider a modification to merge sort in which n/k sublists of...

  • Could you please help me to solve the problem. Also, could you please answer questions in...

    Could you please help me to solve the problem. Also, could you please answer questions in clear hand-writing and show me the full process, thank you (Sometimes I get the answer which was difficult to read).Thanks a lot Suppose we are comparing implementations of two algorithms on the same machine. For input size of n, Algorithm A runs in 8n^2 steps, while Algorithm B runs in 64nlog2(n) steps. For what value n>2, where n is an integer, does Algorithm A...

  • 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...

  • Java Merge sort algorithm

    Implement MERGE-SORT() algorithm that reads from a file named “inputHW02.txt” a list of double numbers (max = 3,000,000 numbers), sorts those numbers and indicates time consumption. This programming question will address the advantage of using iteration loops over recursive calls as well as using INSERTION-SORT() as a procedure in MERGESORT(). Your program must perform the following actions: 1. Opens the given file name and reads all double numbers. For simplicity, we assume this file only contains numbers and nothing else....

  • need help!! java eclipse Write a program to implement bubble sort, insertion sort, selection sort, merge...

    need help!! java eclipse Write a program to implement bubble sort, insertion sort, selection sort, merge sort and quick sort (pivot - first index) algorithms. a) Compute the CPU processing time for all the algorithms for varying input sizes as follows: N-10, 103, 10, 10, and 106 b) Use a random number generator to generate the inputs. Obtain the inputs from the following input ranges: 1- 10, 1 -10, 1 - 10, 1 12 10 c) Write down your results...

  • Implement MERGE-SORT() algorithm that reads from a file named “inputHW02.txt” a list of double numbers (max...

    Implement MERGE-SORT() algorithm that reads from a file named “inputHW02.txt” a list of double numbers (max = 3,000,000 numbers), sorts those numbers and indicates time consumption. This programming question will address the advantage of using iteration loops over recursive calls as well as using INSERTION-SORT() as a procedure in MERGESORT(). Your program must perform the following actions: 1. Opens the given file name and reads all double numbers. For simplicity, we assume this file only contains numbers and nothing else....

  • hheeelppp copying and comparing QUESTION 24 How many comparisons does insertion sort make on an input...

    hheeelppp copying and comparing QUESTION 24 How many comparisons does insertion sort make on an input array that is already sorted? O(1) O(n) o(na) O(log n) 4 QUESTION 25 A linear list of elements in which deletion can be done from one end and insertion can take place only at the othe Queue Stack Array Click Save and Submit to save and submit. Click Save All Answers to save all answers HUAWEI

  • 8 Sorting Algorithms: Bubble, selection, insertion, quick, merge, bucket, radix, counting. 1. A..Which of the above...

    8 Sorting Algorithms: Bubble, selection, insertion, quick, merge, bucket, radix, counting. 1. A..Which of the above sorting algorithms does TimSort use? 2. Which of the above algorithms sort a REVERSE ORDER list in O(n2 ) (worst case)? 3. Which of the above algorithms sort a REVERSE ORDER list in O(nlogn) (worst case)? 4. Which of the above algorithms sort an ordered list , a reverse ordered list, and a random list (all three) in 0(nlogn) (worst case)? 5. Which of...

  • A. What is the time complexity of Insertion Sort? B. Explain why Insertion Sort has the...

    A. What is the time complexity of Insertion Sort? B. Explain why Insertion Sort has the time complexity you listed above in Part A. C. Show the steps followed by the Quicksort algorithm given below in pseudocode when sorting the following array. Algorithm Quicksort (A, left, right) if (left < right) pivot Point + [(left+right)/2] // note central pivot it left - 1 j right + 1 do do iti + 1 while (i < A.size) and (A[i] = A[pivotPoint])...

  • A. What is the time complexity of Merge Sort? B. Explain why Merge Sort has the...

    A. What is the time complexity of Merge Sort? B. Explain why Merge Sort has the time complexity you listed above in Part A. Algorithm Quicksort (A, left, right) if (left < right) pivot Point = [(left+right)/2] 11 note central pivot i left - 1 ja right + 1 do do it i +1 while (i < A.size) and (A[i] SA[pivot Point]) do jj-1 while (j > i) and (A[il > A[pivot Point]) if (i <j) then swap (A[i], Aljl)...

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