A Level Computer Science OCR Practice Exam

Which of the following algorithms is considered inefficient for large data sets due to its quadratic nature?

1. Binary Search

2. Linear Search

3. Quadratic Search

4. Selection Sort

The correct answer is: Quadratic Search

The algorithm considered inefficient for large data sets due to its quadratic nature is Selection Sort. Quadratic algorithms have a time complexity that grows as the square of the input size, which means that as the number of elements increases, the number of operations required to complete the algorithm increases dramatically. Selection Sort works by selecting the smallest (or largest) element from an unsorted portion of the array and placing it at the beginning (or end) of the sorted portion. This process involves a nested loop where for each element in the outer loop, the algorithm goes through the entire list to find the minimum, leading to a time complexity of O(n^2). This makes it significantly slower compared to algorithms with more efficient time complexities, particularly when dealing with large datasets. In contrast, Binary Search operates in logarithmic time, making it extremely efficient for searching through sorted data. Linear Search has a time complexity of O(n), which while not as efficient as logarithmic, is still much better than quadratic complexity for moderately sized datasets. Quadratic Search is not a formal term used in algorithm analysis; hence it does not apply directly in this context. Therefore, Selection Sort is the algorithm that aligns with the criteria of being inefficient for large data sets due to its quadratic nature