(1) Suppose an internet company wants to sort a very large set of numbers, and t

Question

(1) Suppose an internet company wants to sort a very large set of numbers, and the company has multiple powerful computers to work in parallel. Which sorting algorithm should we choose? Please explain your reason.

(2) We know that insertion sorting costs (n 2 ) time for n numbers, because we just simply assume that each “shift” and “comparison” costs constant time. Here “shift” means shift a number from one location to another in the memory, and “comparison” means compare two numbers. But if we specify the running time for each “shift” and “comparison” to be and respectively (which are not constants), what about the total time complexity of insertion sort?

Explanation / Answer

2) actually insertion sort on worst case it takes o(n^2) time complexity it comes because of shifting and compariong operations

actually the time complexity of insertion depends on the number of inversion pairs then only the comparison will comes O(n+d) is the time complexity of the insertion sort algorithm where d is the number of inversion pairs.

so on the same we it is O(alpha+beta) as per you defined in the above problem.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.