Alorithms · Class 12 · CBSE · Science Computer Science
Which statement correctly describes the worst-case time complexity of insertion sort and the situation in which it performs efficiently?
Practice question from Alorithms (Class 12 · CBSE · Science Computer Science), with the correct answer and a step-by-step solution.
medium · MCQ · Q-E5BE84
Which statement correctly describes the worst-case time complexity of insertion sort and the situation in which it performs efficiently?
- A.Its worst-case time complexity is O(log n), and it is efficient for randomly arranged data.
- B.Its worst-case time complexity is O(n), and it is efficient for reverse-sorted data.
- C.Its worst-case time complexity is O(n²), and it is efficient when the data is already or nearly sorted.Correct answer
- D.Its worst-case time complexity is O(n²), and it is efficient only when all elements are identical.
Solution
Insertion sort can shift many elements for each item in the worst case, giving a time complexity of O(n²). When the list is already or nearly sorted, very few shifts are needed, so it performs efficiently.
More from Alorithms
- Which condition is necessary before applying binary search to an array?
- Explain why binary search cannot generally be applied directly to an unsorted array. Also state the worst-case time complexity of linear se…
- What is the array after the first complete pass of selection sort in ascending order on [29, 10, 14, 37, 13]?
- Explain why merge sort is generally preferred over selection sort for sorting a large collection of data. State the time complexity of both…
Practise more Computer Science
Sign up free for adaptive practice on this chapter, with instant feedback and hints on every question.
Start practising freeFree to start · No credit card needed