What is the time complexity of the best-case scenario for Insertion Sort?
Practice Questions
1 question
Q1
What is the time complexity of the best-case scenario for Insertion Sort?
O(n log n)
O(n^2)
O(n)
O(log n)
The best-case time complexity for Insertion Sort is O(n) when the array is already sorted.
Questions & Step-by-step Solutions
1 item
Q
Q: What is the time complexity of the best-case scenario for Insertion Sort?
Solution: The best-case time complexity for Insertion Sort is O(n) when the array is already sorted.
Steps: 5
Step 1: Understand what Insertion Sort does. It sorts an array by building a sorted section one element at a time.
Step 2: Identify the best-case scenario. The best case occurs when the array is already sorted.
Step 3: Analyze how Insertion Sort works in the best case. If the array is sorted, each element is already in the correct position.
Step 4: Count the number of comparisons. In the best case, each element is compared once to the previous element, resulting in n-1 comparisons for n elements.
Step 5: Determine the time complexity. Since the number of comparisons is linear with respect to the number of elements, the time complexity is O(n).
