Question

Determine which computer will process the data below faster. Computer A running insertion sort against a slower computer B running merge sort. They each must sort an array of 50 million numbers. Suppose that computer A executes 10 billion instructions per second and computer B executes only 10 million instructions per second Computer A is 1000 times faster than computer B in raw computing power.

computer A code requires 2n2 instructions to sort n numbers. Suppose that merge sort, using a high-level language with an inefficient compiler, with the resulting code taking 50 nlogn instructions.

Answer 1

Comparing Computer A (insertion sort, 10 billion instructions per second) and Computer B (merge sort, 10 million instructions per second) for sorting 50 million numbers, Computer B sorts faster with a time of 1,196 seconds versus Computer A's 500 seconds, despite the slower instruction rate.

Step-by-step explanation:

We need to determine which computer will process the provided data faster given the sorting algorithms and instruction capabilities. Computer A runs an insertion sort, and Computer B runs a merge sort. We'll consider the number of instructions each computer can execute per second and the efficiency of algorithms in terms of instructions needed.

For Computer A, the insertion sort requires 2n^2 instructions to sort n numbers. Computer A is capable of executing 10 billion instructions per second. For Computer B, the merge sort requires 50n log n instructions, and it executes 10 million instructions per second.

For n = 50 million numbers:

• Computer A = 2(50 million)^2 = 5 trillion instructions required
• Computer B = 50(50 million) log(50 million) ≈ 11.96 trillion instructions required (using log base 2)

To find the time taken for each computer to complete the sort, we divide the instructions required by the number of instructions each computer can process per second:

• Computer A time = 5 trillion / 10 billion = 500 seconds
• Computer B time = 11.96 trillion / 10 million = 1,196 seconds

Even with the slower merge sort algorithm and less raw computing power, Computer B will sort the data faster than Computer A.