Match the LIST-I with LIST-II LIST-I (Algorithm) LIST-II (Complexity) A.…
2025
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(n²) |
C. Quick Sort | III. O(n-1) |
D. Selection Sort | IV. O(n log n) |
Choose the correct answer from the options given below:
- A.
A-III, B-I, C-IV, D-II
- B.
A-II, B-III, C-I, D-IV
- C.
A-I, B-II, C-IV, D-III
- D.
A-II, B-III, C-IV, D-I
Attempted by 200 students.
Show answer & explanation
Correct answer: A
Answer: Insertion Sort → O(n-1), Binary Search → O(log n), Quick Sort → O(n log n), Selection Sort → O(n^2).
Insertion Sort — O(n-1): Represents the linear best case (for example, when the input is already sorted), where about n−1 comparisons occur.
Binary Search — O(log n): Halves the search interval each step, giving logarithmic time.
Quick Sort — O(n log n): Average-case complexity is n log n due to partitioning and recursive sorting of subarrays.
Selection Sort — O(n^2): Finds the minimum repeatedly, resulting in quadratic comparisons regardless of initial order.
Brief note on common confusions: Insertion sort can be O(n) in the best case but O(n^2) on average or worst case; selection sort is consistently O(n^2); binary search is logarithmic; quick sort is typically O(n log n) on average.
A video solution is available for this question — log in and enroll to watch it.