Match the LIST-I with LIST-II

LIST - I Algorithm		LIST - II Complexity
A.	Insertion Sort	I.	O(log n)
B.	Binary Search	II.	O(n2)
C.	Quick Sort	III.	O(n - 1)
D.	Selection Sort	IV.	O(n log n)

Choose the correct answer from the options given below:

The correct answer is Option 1: A - III, B - I, C - IV, D - II.

Key Points

• Insertion Sort: The complexity is O(n-1) in the average and worst case, where n is the number of elements. This is because each element might need to be compared with all other elements in the worst-case scenario.
• Binary Search: The complexity is O(log n). This logarithmic complexity comes from the fact that the algorithm repeatedly divides the search interval in half.
• Quick Sort: The average-case complexity is O(n log n). This is because the algorithm divides the array into two parts and recursively sorts them.
• Selection Sort: The complexity is O(n²). In each iteration, the algorithm selects the smallest element and places it in the correct position, leading to quadratic time complexity.

Additional Information

• Insertion Sort: This algorithm is efficient for small datasets or nearly sorted data.
• Binary Search: This algorithm requires the dataset to be sorted before it can be applied.
• Quick Sort: Despite its average-case efficiency, its worst-case complexity is O(n²), but this can be mitigated with good pivot selection strategies.
• Selection Sort: It performs well on small lists but is inefficient on large lists compared to more advanced algorithms like Quick Sort or Merge Sort.