Problem of the Day
Wednesday, April 30, 2025
Problem:
A Selection Sort algorithm (blue data points in the graph below) is run on one computer, and an Insertion Sort algorithm (orange data points) is run on a different computer. The times for each algorithm to sort an increasing number of data elements is plotted, and the trendlines for those data points are quadratic (2nd-order polynomials).
What can be concluded about the the Big-O performance of these two algorithms?
- The Insertion Sort (orange data) is a better algorithm because it takes less time.
- The Selection Sort (blue data) is a better algorithm because it has a steeper curve.
- The Big-O performance of the Insertion Sort (orange data) is better because the sorting occurs more quickly.
- The Big-O performance of the two algorithms is the same.
- The Big-O performance of the two algorithms can't be compared because they were run on different computers.
The correct answer is d. Big-O performance has to do with how an algorithm's time to complete scales with size of data, and is not related to absolute run time. Selection Sort and Insertion Sort are both O(n2) algorithms where performance time increases as the square of the array size. They have the same Big-O performance.