Given: 10,000,000 unsorted numbers; 10,000 greatest numbers; each operation takes 0.0001 milliseconds.

1. How long will the original program take?

Assumption: The program uses a comparison-based sorting algorithm such as Merge Sort, whose time complexity is O(n log₂ n). For this simplified calculation, each estimated operation is charged the given cost of 0.0001 ms.

Step 1: Sort all 10,000,000 numbers

n log₂ n = 10,000,000 × log₂(10,000,000)

≈ 10,000,000 × 23.2535 = 232,535,000 operations

232,535,000 × 0.0001 ms = 23,253.5 ms = 23.2535 seconds

Step 2: Put the greatest 10,000 numbers into a linked list

Assuming one operation per selected number: 10,000 × 0.0001 ms = 1 ms = 0.001 seconds.

Step 3: Randomly print all 10,000,000 numbers

10,000,000 × 0.0001 ms = 1,000 ms = 1 second.

Total time for the original program

23.2535 + 0.001 + 1 = 24.2545 seconds.

Answer 1: Approximately 24.25 seconds.

2. How can the program be more efficient and scalable?

Instead of sorting all 10,000,000 numbers, use Quickselect to identify the 10,000 greatest numbers. Quickselect has expected O(n) time complexity, so it avoids fully sorting data that will not be printed. Then randomly shuffle the selected 10,000 numbers using Fisher–Yates and print them. This preserves the required functionality: the output contains the 10,000 greatest values in random order.

Estimated new time

For a simplified estimate, count about one operation per input number for selection, plus about one operation per selected number for shuffling:

10,000,000 + 10,000 = 10,010,000 operations

10,010,000 × 0.0001 ms = 1,001 ms = 1.001 seconds.

Answer 2: Approximately 1.00 second under the simplified operation-count assumption.

Conclusion

The original approach takes approximately 24.25 seconds because it sorts and prints all the data. The improved approach uses Quickselect to find only the greatest 10,000 values, shuffles those values, and prints them. Its estimated time is about 1.00 second. Actual running time depends on the algorithm implementation and on what counts as an individual operation; Quickselect is O(n) on average, but its worst-case time can be O(n²) unless a worst-case-linear selection algorithm is used.

Rahma Salim Al-shereiqi

--

1